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\) 时：

因为 \(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}\) 时：

因为 \(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)\) 的时间复杂度里计算出它的答案。怎么求呢？

所以答案就是 \(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";
        }
    }
}