题意
给定正整数 \(n\)，询问是否存在 \(k \ge 2\)，使得 \(n\) 可以表示成 \(k\) 个对 \(k\) 取模后的结果互不相同的正整数之和。
（\(1 \le T \le 10^5, 2 \le n \le 10^{18}\)）。
题解
通过分析可得，对于正整数 \(n\)，\(k\) 满足要求的充要条件为
按 \(k\) 的奇偶性进行分类讨论，设 \(n = x \cdot 2^y\)，其中 \(x\) 为奇数。
\(k\) 为偶数
那么上式可化为
容易发现 \(2p + k + 1\) 为奇数。可得上式成立当且仅当 \(x = 2p + k + 1 \land \dfrac{k}{2} = y \Rightarrow k = 2^{y + 1}\)。观察什么时候会无解，如果不存在 \(p \in \mathbb{N}\) 使得 \(2p + k + 1 = x\) 即 \(k + 1 > x\)，那么无解。
\(k\) 为奇数
那么上式可化为
通过分析可以得出该式有解的充要条件为存在 \(p \in \mathbb{N}\) 使得 \(p + \dfrac{k + 1}{2} = \dfrac{n}{k}\) 且 \(k \geqslant 2\)，其中 \(\dfrac{k + 1}{2} \leqslant \dfrac{n}{k} \Leftrightarrow k\left(k + 1\right) \leqslant 2n\)。
现在将两种情况合并到一起考虑，可以发现，如果 \(x \geqslant 2^{y + 1}\)，那么 \(k\) 为偶数的情况一定有解。如果 \(x < 2^{y + 1}\)，那么
所以该种情况无解当且仅当 \(x == 1\)。
综上所述
- 如果 \(n = 2^y\)，那么无解；
- 如果 \(n = x \cdot 2^y \land x \geqslant 2^{y + 1}\)，那么 \(k = 2^{y + 1}\) 有解；
- 如果 \(n = x \cdot 2^y \land x < 2^{y + 1}\)，那么 \(k = x\) 有解；
观察到 \(2^y\) 为 \(\operatorname{lowbit}(n)\)，可以 \(\mathcal{O}(1)\) 求解。
Code
//Codeforces - 1656D
#include <bits/stdc++.h>
typedef long long valueType;
valueType lowBit(valueType x) {
return x & -x;
}
int main() {
valueType T;
std::cin >> T;
for (valueType testcase = 0; testcase < T; ++testcase) {
valueType N;
std::cin >> N;
valueType const bit = lowBit(N);
valueType const x = N / bit, y = bit << 1;
if (x == 1) {
std::cout << -1 << '\mathbb{N}';
} else {
std::cout << std::min(x, y) << '\mathbb{N}';
}
}
std::cout << std::flush;
return 0;
}