E2
按值域分治的技巧
前置 : \(f(k , n) = 1 + k + k ^ 2 + ... + k ^ n\)
\(①\) : 假设答案最终的 \(n = 2\) , 对于 \(1 + k + k ^ 2\) , 我们在 \([2 , 10^9]\) 的范围二分 \(k\) 即可
\(②\) : 假设答案最终的 \(n > 2\) , 那么形式至少是 \(1 + k + k ^ 2 + k ^ 3\) , 由于 \(k ^ 3\) 的存在 , \(k\)的范围只能是 \([2 , 10^6]\) , 那么我们枚举 \(k\) , 对于每种 \(k\) , 递增枚举 \(n\) , 不断向 \(set\) 添加\(f(k , n)\) 的值 , 知道\(f(k , n) > 10^{18}\) , 由于指数增加 , 最终 \(set\) 中的个数为\(O(klogk) , k = 10^6\)
对于每个 \(x\) , 先尝试 \(①\) , 再尝试 \(②\) 即可
#include <bits/stdc++.h>
using ll = long long;
const ll INF = 1E18;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::set<ll> p;
for(ll k = 2 ; k <= 1E6 ; ++k) {
ll w = 1 + k + k * k + k * k * k;
p.insert(w);
ll base = k * k * k;
while(true) {
if (base <= INF / k) {
base *= k;
}
else break;
if (w + base <= INF) {
w += base;
p.insert(w);
}
else break;
}
}
int t;
std::cin >> t;
while (t--) {
ll x ;
std::cin >> x;
ll l = 2 , r = 1E9;
while(l < r) {
ll mid = l + r >> 1;
if(1 + mid + mid * mid >= x) r = mid;
else l = mid + 1;
}
bool ok = false;
if(1 + r + r * r == x) {
ok = true;
}
if(!ok && p.count(x)) {
ok = true;
}
if(ok) std::cout << "YES\n";
else std::cout << "NO\n";
}
return 0;
}