Codeforces 233B Non-square Equation(数学)解题报告

2016-10-07 705 次浏览 解题报告

题面

题意

给定一个方程,求出 x 的最小正整数解,如果不存在,则输出 -1 。

解题思路

注意到题目中的 n 的最大值是 $10^{18}$ ,由公式可以估算出 x 的最大值是 $10^{9}$ ,直接暴力显然会超时。观察题目给出的方程:

$$x^{2} + s(x) \centerdot x - n = 0$$

注意 s(x) 函数,可以发现 s(x) 在 x 取得最大值,即 x = 999999999 时相应地取得最大值,即 81。于是,我们可以去枚举 s(x) ,计算相应的 x 能否使方程左右两边相等,这样就能大大降低复杂度。我们将原方程化为左边是 x 的方程:

$x^{2} + s(x) \centerdot x - n + \frac{s(x)^{2}}{4} = \frac{s(x)^{2}}{4}\tag{1}$

$(x + \frac{s(x)}{2})^{2} = \frac{s(x)^{2}}{4} + n\tag{2}$

$x + \frac{s(x)}{2} = \sqrt{\frac{s(x)^{2}}{4} + n}\tag{3}$

$x = \sqrt{\frac{s(x)^{2}}{4} + n} - \frac{s(x)}{2}\tag{4}$

这样,我们只需要从 1 到 81 枚举所有 s(x),计算出相应的 x,代入方程比较是否相等即可。

参考代码

#include <cstdio>
#include <cmath>
using namespace std;

// s(x) 函数
int s(long long x) {
    int sum = 0;
    while(x) {
        sum += x%10;
        x /= 10;
    }

    return sum;
}

int main(int argc, char const *argv[]) {
    long long n, ans = -1;
    scanf("%lld", &n);
    for(int i=1; i<=81; ++i) {
        long long x = sqrt(i*i/4+n) - i/2;
        int sx = s(x);
        if(x*x+sx*x-n == 0) {
            ans = x;
            break;
        }
    }
    printf("%lld\n", ans);
    
    return 0;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2016/10/07/codeforces-233b.dream

还不快抢沙发

添加新评论