题意是有一个等式：x^2+s(x, m)*x-n = 0

s(x, m)表示把x写成m进制时，每个位数相加的和

找到满足条件的最小正整数x，如果不存在，输出-1

很容易想到把等式转换为x+s(x, m) = n/x

所以可以知道n是x的整数倍，且n>x*x

但仅仅是这样时间复杂度是降不下来的

做比赛的时候一直没有想出来，快结束的时候小伙伴王烯想出了一个办法：枚举s(x, m)的值，可以发现这个值的范围是很小的

我们令k = s(x, m), 则可以将上式转为一个二元一次方程:x^2+kx-n = 0

枚举k后，解出x，判断是否满足原方程即可

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
LL n, m;
LL ss(LL x, LL m) {
	LL ans = 0;
	while(x) {
		ans += x%m;
		x /= m;
	}
	return ans;
}
int main(void) {
	int T;
	scanf("%d", &T);
	while(T--) {
        cin >> n >> m;
		bool ok = true;
		for(LL s=1; s<=2000; ++s) {
			LL x = (-s+sqrt(s*s+4*n))/2;
			if(x*x + ss(x, m)*x == n) {
				cout << x << endl;
				ok = false;
				break;
			} 
		}
		if(ok) cout << -1 << endl;
	}
	return 0;
}