Statement
\(T\) 次给定整数 \(n\)，判断是否存在 \(q, k \ge 2\) 使得 \(1 + q + q^2 + \cdots + q^k = n\)。
\(1 \le T \le {10^4}\)，\(1 \le n \le {10}^{18}\)。
Solution
考虑弱化问题 CF1846E1。这里 \(1 \le n \le {10}^6\)。
设 \(w = {10}^6\)，可能的 \(n\) 的数量是
\[\begin{aligned}
s&=\log_2 w + \log_3 w + \cdots + \log_{\sqrt{w}} w\\
&= \ln w (\frac{1}{\ln2} + \frac{1}{\ln3} + \cdots + \frac{1}{\ln\sqrt{w}}).\\
\end{aligned}
\]
这里 \(s \approx 2453.4073\)。Link.
打表存进 set 里面即可。
但是这题 \(1 \le n \le {10}^{18} = w\)，估计一下必然超时了。
注意到
\[999999 ^3 + 999999 ^2 + 999999 + 1 = 999,998,000,002,000,000 < {10}^{18}.
\]
\[1000000 ^3 + 1000000 ^2 + 1000000 + 1 = 1,000,001,000,001,000,001 > {10}^{18}.
\]
大可以枚举 \(2 \sim {10}^6 - 1\) 的数作为 \(q\)，把所有合法的 \(n\) 存进 set 容器。
可能的 \(n\) 的数量是
\[\begin{aligned}
S &= \log_2 w + \log_3 w + \cdots + \log_{\sqrt[3]{w}} w \\
&= \ln w (\frac{1}{\ln2} + \frac{1}{\ln3} + \cdots + \frac{1}{\ln\sqrt[3]{w}}).\\
\end{aligned}
\]
这里 \(S \approx 3.258 \times 10^6\)。Link.
对于不小于 \({10}^6\) 的数怎么做？
注意到它们已经没有 \(k \ge 3\) 的解了。具体地，假设存在一个 \(q_0\) 和 \(k = 2\) 使得 \(q_0^2 + q_0 + 1 = n\)，容易得到（另一根舍去）
\[q_0 = \frac{-1 + \sqrt{4n - 3}}{2}.
\]
求出 \(q_0\) 后再代回方程验证即可。
这样，我们在 \(O(S \log S + T\log S)\) 的时间内解决了此问题。
Code
#include <bits/stdc++.h>
using namespace std;
set <__int128> s;
const __int128 INF = 1000000000000000000ll;
int main() {
for(long long i = 2; i <= 1000000; ++i) {
__int128 j = i + 1;
__int128 l = i * i;
while(j + l <= INF) {
j += l;
l *= i;
s.insert(j);
}
}
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt;
cin >> tt;
while(tt--) {
long long x;
cin >> x;
if(s.count(x)) {
cout << "YES" << endl;
}
else if(x >= 1000000000000ll){
long long delta = 1 - 4 * (1 - x);
long long x1 = 0.5 * (-1 + sqrt(delta));
if(x1 * x1 + x1 + 1 == x) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
else {
cout << "NO" << endl;
}
}
}