CF1656D K-good 题解
题目大意
给出 \(t\) 个整数 \(n\)，对于每一个 \(n\) 找出一个大于等于 \(2\) 的整数 \(k\)，使得 \(n\) 可以表示成 \(k\) 个mod \(k\) 的结果互不相同的正整数之和。
\(1 \le t \le 10^5, 2 \le n \le 10^{18}\)。
题解
我们先将题意再次化简，可以得到，我们实际上就是要找一个 \(k\)，使得 \(n = p \cdot k + \frac{k(k + 1)}{2}\)（\(p\) 为非负整数）。
我们通过观察可以发现，\(n\) 为奇数还是偶数，与它的性质和最终答案有直接联系，所以我们分情况讨论。
\(n\) 为奇数
当 \(n\) 为奇数时，我们不难发现，只要令 \(k = 2\) 就可以满足条件。因为任意一个奇数都能写成 \(2p + 1\) 即 \(2 \cdot p + \frac{1 \times 2}{2}\) 的形式。所以对于 \(n\) 为奇数的情况，直接输出 \(2\) 即可。
\(n\) 为偶数
当 \(n\) 为偶数时，我们可以将 \(n\) 换一种写法，写作 \(x \cdot 2^y\)（\(x\) 为奇数，\(y\) 为正整数）。
可是我们为什么要这么写呢？这么写有什么用呢？
其实，在瞪眼观察法 摆烂分神法 后，我们可以非常容易地明白：这个题奇数与偶数的解决方法不太一样，所以这就是我们的切入点。而 \(x \cdot 2^y\) 就很好地将一个数的奇数与偶数部分分开了。那么我们利用这个式子继续往下走：
到了这里，我们就可以继续利用奇偶数分情况讨论的方法，进一步进行化简：
当 \(k = x\) 时：
\[\begin{aligned} x \cdot 2^{y + 1} &= x(2p + x + 1)\\ 2^{y + 1} &= 2p + x + 1\\ \end{aligned}\]因为 \(x\) 为奇数，所以 \(x + 1\) 为偶数，又因为 \(2p\) 为偶数，所以只要保证 \(x + 1 \le 2^{y + 1}\)，就一定有 \(2p + x + 1 = 2^{y + 1}\) 。此时我们的 \(k = x\)，也就是说只要 \(x \le 2^{y + 1}\) ，答案就是 \(x\)。
当 \(k = 2^{y + 1}\) 时：
\[\begin{aligned} x \cdot 2^{y + 1} &= 2^{y + 1}(2p + 2^{y + 1} + 1)\\ x &= 2p + 2^{y + 1} + 1\\ \end{aligned}\]因为 \(2^{y + 1}\) 为偶数，所以 \(2^{y + 1} + 1\) 为奇数，又因为 \(2p\) 为偶数，所以只要保证 \(2^{y + 1} \le x\)，就一定有 \(2p + 2^{y + 1} + 1 = x\)。此时我们的 \(k = 2^{y + 1}\)，也就是说只要 \(2^{y + 1} \le x\)，答案就是 \(2^{y + 1}\)。
综上所述：
答案就是 \(x\) 与 \(2^{y + 1}\) 中的较小值。所以我们对于每一个 \(n\)，可以在 \(O(1)\) 的时间复杂度里计算出它的答案。怎么求呢？
\[\begin{aligned} 2^y &= lowbit(x) = x \& (-x) \\ 2^{y + 1} &= 2 \cdot lowbit(x) \\ x &= \frac{n}{2^y} = \frac{n}{lowbit(x)} \\ \end{aligned}\]所以答案就是 \(min(2 \cdot lowbit(x), \frac{n}{lowbit(x)})\)。
可是如果你就这样交上去，会喜提一个 \(WA\)。
为什么呢？
注意题里所说的 \(k >= 2\)，所以你还需要特判一下 \(min = 1\) 的情况，并输出 \(-1\)，这样就能愉快地 \(AC\) 啦。
代码
这么简单的题还要看代码吗？就只有20行自己写写吧 \(QWQ\)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int T, n;
signed main() {
ios::sync_with_stdio(0);
cin >> T;
for(int i = 1; i <= T; ++ i) {
cin >> n;
if((n & 1) == 1)
cout << 2 << '\n';
else {
int lowbit = n & (-n), minn = min(lowbit * 2, n / lowbit);
if(minn != 1) cout << minn << "\n";
else cout << "-1\n";
}
}
}