CF1656D K-good

题目链接

分析

一个数字 $n$ 是 $k-good$ 的，则它满足如下 2 个必要条件：

$n \geq 1+2+…+k=\frac{k(1+k)}{2}$
$n \equiv 1+2+…+k \equiv \frac{k(1+k)}{2}(mod\ k)$

若 $k$ 是偶数，则第二个必要条件可转化为 $n \equiv \frac{k(1+k)}{2} \equiv \frac{k}{2}(1+k) \equiv \frac{k}{2} (mod\ k)$，即 $2n\equiv 0(mod\ k)$。另，由第二个必要条件可得 $n \neq 0(mod\ k)$。在满足这两个条件的前提下，寻找最小的 $k$（为了尽可能满足第一个必要条件）：设将 $n$ 质因数分解后，$2$ 的指数为 $v_2$（即$n=2^{v_2}3^{v_3}5^{v_5}…$），则 $k_{min}=2^{v_2+1}$。若 $k_{min}$ 仍不满足第一个必要条件，则考虑 $k$ 为奇数的情况。
若 $k$ 是奇数，则第二个必要条件可转化为 $n \equiv \frac{k(k+1)}{2}(mod\ k)$，即 $n=\frac{k(k+1)}{2}+tk$，$2n=k(k+1)+2tk=k(k+1+2t)=kk_1$（设 $k_1=k+1+2t$，易知其为偶数），且由于策略 2 是由于策略 1 失效才进入，故明显有 $n<\frac{k_1(k_1+1)}{2}, 2n=kk_1<k_1(k_1+1), k<k_1+1$，且由于 $k$ 是奇数，$k_1$ 是偶数，故有 $k < k_1$，则 $\frac{k(k+1)}{2} \leq \frac{kk_1}{2} = n$，即 $k$ 肯定满足必要条件一（唯一的限制条件是 $k>1$）。
现在考虑答案是 -1 的情况。若 $n=2^t$，对于策略 1，$k_{min}=2^{t+1}>n$，不满足必要条件一；对于策略 2，由于 $k$ 是奇数，且 $2n=kk_1=2^{t+1}$，故 $k$ 只能是 1，不成立。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 110;

int main(){
    // freopen("in.txt", "r", stdin);
 
    int t;
    scanf("%d",&t);
    while(t--){
        LL n;
        scanf("%lld",&n);
        LL ji=n;
        while(ji%2==0)  ji/=2;
        if(ji==1){
            puts("-1");
            continue;
        }

        LL k=n/ji*2;
        if(k<=2e9 && k*(1+k)/2<=n){
            printf("%lld\n", k);
        }
        else{
            printf("%lld\n", ji);
        }
    }
 
    return 0;
}