CF-CodeTon Round1-D.K-good

题意

将一个数分为k个数的和，其中k个数%k互不相等。

题解

n 是 k-good 当且仅当:
条件1：n≥1+2+…+k=k(k+1)2。

(如果连续最小的k个数都比当前的数大，那么当然不可以了)
条件2：n≡1+2+…+k≡k(k+1)2(modk)。

先考虑满足k个数%k互不相等的构造方法：连续的整数%k一定互不相同。

那么我们可以构造出公式：n=（1+k）k/2+mk（这里的m*k的意思是把其中m项都加上k）

将分式两边同乘2并提取公因式：2n=（1+k）k+2mk=k（1+k+2*m）
这里可以发现，k与（1+k+2m）奇偶性不同，并且m、k可以取任何值。

那么本题就变成了：将2n构造为奇数乘偶数的形式。

2n=f(奇)f(偶)
考虑将2n质因数分解（只将2分解出来）后得到2n= f 2^q 其中2^q一定为偶数数 f一定为奇数，构造完毕，但是要注意如果2*n为2的次幂那就无解，因为无法分为奇数乘偶数的形式。

同时要满足k尽量小（条件1），所以要取两者小的一个数字。

#include
using namespace std;
typedef long long ll;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        ll n;
        scanf("%lld", &n);
        n *= 2;
        ll base = 1;
        while (n % 2 == 0)
        {
            n /= 2;
            base *= 2;
        }
        if (n == 1)
            printf("-1\n");
        else 
        {  
            printf("%lld\n", min(base, n));
        }
    }
}