E2. Rudolf and Snowflakes (hard version) - 题解
比赛与标签
比赛: Codeforces Round 883 (Div. 3) 标签: binary search, brute force, implementation, math 难度: *1800
雪花的秘密喵~
嗨，你好呀，我是猫娘~！今天我们来研究一个超级可爱的题目——鲁道夫的雪花！❄️
题目说呀，有一种特殊的雪花图，它是这样生成的：
- 一开始只有一个中心点。
- 然后这个中心点，会向外连接
k个新的点（这里要求k > 1呐）。 - 之后，每一个只连接了一个邻居的“末梢”点，都会再各自连接
k个新的点。这个步骤至少要进行一次。
我们把从中心点开始，向外生长了一层的点集叫做第1层（有 k 个点），再生长一层叫做第2层（有 k*k 个点），以此类推。如果这个过程进行了 d 次（d 是雪花的“深度”），那么总的点数 n 就是： n = 1 (中心点) + k (第1层) + k^2 (第2层) + ... + k^d (第d层)
题目要求 d 至少是 2（因为规则里说“这个步骤应该做至少一次”，也就是至少要生长出第2层）。
所以，问题就变成了：给你一个数字 n，问是否存在一对整数 k > 1 和 d >= 2，使得上面的等式成立呢？如果存在，就输出 "YES"，否则就输出 "NO" 的说。
一起来解开谜题吧！
这个题目看起来有点吓人，n 最大可以到 10^{18} 这么大！直接去枚举 k 和 d 肯定会超时的喵。不过别担心，我们猫娘有聪明的办法！
我们把问题分成两种情况来讨论，这样就简单多啦！
情况一：当雪花深度 d = 2 时
这是最浅的雪花啦~ 它的顶点数公式是 n = 1 + k + k^2。 喵~ 这是一个关于 k 的一元二次方程！我们把它整理一下： k^2 + k + (1 - n) = 0
还记得初中学过的求根公式吗？k = (-b ± sqrt(b^2 - 4ac)) / (2a)。 代入 a=1, b=1, c=1-n，我们得到： k = (-1 ± sqrt(1^2 - 4 * 1 * (1 - n))) / 2k = (-1 ± sqrt(1 - 4 + 4n)) / 2k = (-1 ± sqrt(4n - 3)) / 2
因为 k 必须是大于1的正整数，所以我们只取 + 号。那么 k = (-1 + sqrt(4n - 3)) / 2。 为了让 k 是一个整数，4n - 3 必须是一个完全平方数！比如说，m^2 = 4n - 3。 这样 k = (m - 1) / 2。 同时，我们还要求 k > 1，也就是说 (m - 1) / 2 > 1，解出来就是 m > 3。 所以，对于 d=2 的情况，我们只需要检查：
4n - 3是不是一个完全平方数m^2。- 这个平方根
m是不是大于 3。 (m - 1)是不是偶数（m^2 = 4n - 3是奇数，所以m必然是奇数，m-1必然是偶数，这一步其实可以省略检查）。
这个检查非常快，我们先搞定它！如果满足条件，那答案就是 "YES" 啦！
情况二：当雪花深度 d >= 3 时
如果 d=2 不行，我们再来看看更深的雪花。 公式是 n = 1 + k + k^2 + ... + k^d。 我们发现，对于一个固定的深度 d，当 k 增大的时候，n 也会飞快地增大。这是一个单调递增的关系！喵~ 这不就是二分查找的完美应用场景嘛！
那 d 的范围是多少呢？因为 k > 1，所以 k 最小是 2。 n = 1 + k + ... + k^d > k^d >= 2^d 所以 2^d < n，两边取对数，d < log2(n)。 当 n = 10^{18} 时，log2(10^{18}) 大约是 59.79。所以 d 最大也就在 60 左右。 哇！d 的范围其实很小！我们可以从 d=3 循环到 60。
对于每一个 d，我们来二分查找对应的 k：
- 确定
k的范围：k的下界是2。上界呢？因为k^d < n，所以k < n^(1/d)。我们可以把上界设为pow(n, 1.0/d) + 2，加个2更保险一点。 - 二分过程：
- 取中间值
mid_k。 - 计算
sum = 1 + mid_k + mid_k^2 + ... + mid_k^d。 - 注意！
n很大，计算sum的时候，mid_k的高次幂很容易就溢出了！所以我们要在每一步乘法和加法前都检查一下，如果current_term * mid_k会超过n，或者current_sum + new_term会超过n，那就说明这个mid_k太大了，可以直接剪枝。 - 如果
sum == n，太棒了！找到了一组解，答案是 "YES"！ - 如果
sum < n，说明mid_k太小了，我们应该在右半边区间[mid_k + 1, high]继续找。 - 如果
sum > n(或者计算时溢出了)，说明mid_k太大了，我们应该在左半边区间[low, mid_k - 1]继续找。
- 取中间值
如果遍历了所有可能的 d (从3到60)，都没有找到合适的 k，那么就真的没有办法组成雪花了，答案就是 "NO" 的说。
总结一下我们的策略：
- 先用公式快速判断
d=2的情况。 - 如果不行，再循环
d从3到60。 - 在循环内部，对
k进行二分查找。 - 如果以上都找不到，就输出 "NO"。
这样一来，问题就迎刃而解啦！是不是很清晰了呢，喵~？
让我们写下来吧！
// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <cmath>
// 解决单个测试用例的函数喵~
void solve() {
long long n;
std::cin >> n;
// 一个雪花的总顶点数 n = 1 + k + k^2 + ... + k^d，其中 k > 1, d >= 2。
// 最小的雪花是 k=2, d=2，此时 n = 1+2+4=7。
// 如果 n < 7，那肯定组不成雪花啦！
if (n < 7) {
std::cout << "NO\n";
return;
}
// 情况一：深度 d = 2
// 方程是 n = 1 + k + k^2。
// 整理成关于 k 的一元二次方程: k^2 + k + (1-n) = 0。
// 用求根公式解 k: k = (-1 + sqrt(4n - 3)) / 2。
// 要想 k 是一个大于1的整数，那么 4n-3 必须是一个完全平方数 m^2，并且 m > 3。
long long discriminant = 4 * n - 3;
if (discriminant >= 0) { // 判别式必须非负
// 这里用 long double 的 sqrtl 来提高精度，防止大数出错
long long root = round(sqrtl(discriminant));
if (root * root == discriminant) { // 检查是不是完美的平方数
// 如果 root^2 = 4n-3，那么 root 必须是奇数，所以 (root-1) 一定是偶数。
// 我们只需要检查 k > 1，也就是 (root-1)/2 > 1 => root > 3。
if (root > 3 && (root - 1) % 2 == 0) {
std::cout << "YES\n";
return;
}
}
}
// 情况二：深度 d >= 3
// 对于固定的 d，n 是 k 的单调递增函数。我们可以对 k 进行二分查找。
// d 的最大值不会超过 log2(n)，对于 n=10^18 来说大约是 60。
for (int d = 3; d <= 60; ++d) {
long long low = 2; // k 的下界是 2
// k 的上界大约是 n^(1/d)。为了保险，可以稍微放大一点。
long long high = static_cast<long long>(pow(n, 1.0L / d)) + 2;
if (high < low) continue; // 如果上界比下界还小，就没必要搜了
while (low <= high) {
long long k = low + (high - low) / 2;
if (k < 2) { // 确保 k > 1
low = 2;
if (low > high) break; // 如果 low 调整后大于 high，就退出循环
k = low + (high - low) / 2; // 重新计算 k
}
// 计算等比数列的和 1 + k + ... + k^d，同时检查溢出。
long long current_sum = 1;
long long current_term = 1;
bool too_large = false;
for (int i = 1; i <= d; ++i) {
// 检查 current_term * k 是否会溢出或者超过 n。
// n / k < current_term 是一个防止溢出的好技巧！
if (k > 0 && current_term > n / k) {
too_large = true;
break;
}
current_term *= k;
// 检查 current_sum + current_term 是否会超过 n。
if (current_sum > n - current_term) {
too_large = true;
break;
}
current_sum += current_term;
}
if (too_large) { // 如果和太大了（或溢出了）
high = k - 1; // k 需要减小
} else if (current_sum == n) { // 找到了！喵~
std::cout << "YES\n";
return;
} else { // current_sum < n
low = k + 1; // k 需要增大
}
}
}
// 所有情况都试过了，还是不行，那就是真的不行了。
std::cout << "NO\n";
}
int main() {
// 加速输入输出，对付大数据量测试用例的必备技巧喵~
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}复杂度分析 - 我们的算法跑得有多快呢？
时间复杂度: O(log(n) * log(n)) 的说。 对于每个测试用例，我们首先进行
d=2的判断，这几乎是O(1)的（sqrt函数非常快）。然后我们有一个循环，d从3到60左右。这个循环的次数可以看作是O(log n)。在循环内部，我们对k进行二分查找。k的搜索范围最大是n^(1/d)，所以二分查找需要log(n^(1/d)) = (1/d)log(n)次比较。每次比较，我们需要计算一个d项的等比数列和，这需要O(d)的时间。所以总的时间复杂度大约是sum_{d=3 to log(n)} O(d * (1/d)log(n)) = sum_{d=3 to log(n)} O(log n) = O(log(n) * log(n))。对于10^{18}的n来说，这个速度是飞快的喵！空间复杂度: O(1) 的说。 我们在解决问题时只用到了几个变量来存储
n,k,d和一些中间结果，没有使用任何随输入规模增大的数据结构。所以空间是恒定的，非常节省内存呐！
知识点与总结 - 这次我们学到了什么喵？
这次的雪花之旅，我们收获满满呀！
- 数学建模能力: 将图形的生成规则，巧妙地转化为一个优美的等比数列求和公式
n = 1 + k + ... + k^d，这是解题的第一步，也是最关键的一步！ - 分类讨论思想: 面对一个复杂的问题，把它拆分成几个更简单的小问题来解决，是一个非常有效的策略！这里我们把问题分成了
d=2和d>=3两种情况，前者用数学公式直接求解，后者用算法解决，思路一下子就清晰了。 - 二分查找的应用: 当你发现问题具有单调性时（一个变量增大，结果也随之单调变化），一定要想想二分查找！它可以把线性的搜索时间，降低到对数级别，超级高效！
- 大数与溢出处理: 处理
long long级别的大数据时，要时刻对溢出保持警惕！像a * b > n这样的判断，最好写成a > n / b的形式，这是防止溢出的一个重要技巧哦。 - 范围分析: 确定循环和搜索的边界（比如
d的上界和k的上界）是优化算法和保证正确性的基础。
希望这篇题解能帮助你理解这个有趣的题目！只要我们勤于思考，再难的问题也能像解开毛线球一样，找到线头的说！加油，未来的算法大师！喵~