题面

题意

给定一个方程，求出 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;
}