做法
奇偶性判定好题。
\(Case1:\) \(n\)为奇数
很显然,\(n\)为奇数时一定可以拆分成两个数\(x\)和\(y\),且\(x\)为奇数,\(y\)为偶数,发现\(x \mod 2=1,y\mod 2=0\),\(k\)也刚好位\(2\),所以当\(n\)为奇数时就直接输出\(2\)。
\(Case2:\) \(n\)为偶数
设\(k\)个数为\(a_1,a_2,...,a_k\),所以有\(a_1+a_2+..+a_k=n\),由于题目说\(a_1\mod k,a_2 \mod k,...,a_k\mod k\)互不相同,所以这些数\(\mod k\)一定为\(0,1,2,...,k\)且不重不漏。
那么考虑拆分\(a_i\),设\(a_i=b_i\times k+c_i(c_i=a_i \mod k)\),那么\(a_1+a_2+...+a_k=n\)就可以转化为\((b_1\times k+b_2 \times k+...+b_k\times k)+(c_1+c_2+...+c_k)\)。
因为\(c_1+c_2+...+c_k\)一定等于\(0+1+...+k-1\),等差数列求和得\(\frac{(0+k-1)\times k}{2}=\frac{(k-1)\times k}{2}\),再把\(b_1\times k+b_2\times k+...+b_k\times k\)提取公因式得\(k\times(b_1+b_2+...+b_k)\),再设\(b_1+b_2+...+b_k=x\),所以\(b_1\times k+b_2\times k+...+b_k\times k=k\times x\)。
所以\(n=\frac{(k-1)\times k}{2}+k\times x\),将上式化简得\(2\times n=k\times(k+2\times x-1)\),然后我们发现一个结论:\(k\)和\(k+2\times x-1\)中一定有一个为偶数,因为\(2\times x-1\)一定为奇数,所以如果\(k\)为偶数,上述结论肯定成立,如果\(k\)为奇数,那么\(k+2\times x-1\)一定为偶数,
故得证。
所以我们把\(2\times n\)拆成\(2^{p}+q\),使得\(2^{p}|2\times n-q\),而\(2^{p+1}\nmid 2\times n-q\)且\(q< 2^{p}\),那么这样做显然\(q\)为奇数,这样拆是把这个数拆成偶数乘奇数的形式。
设\(a=2^{p},b=q\),那么可以证明\(k\)一定可以等于\(min(a,b)\) ,如果这样拆后\(min(a,b) \le 1\)就说明无解(因为题目中说的是\(2\le k\),与题目矛盾),输出\(-1\),否则就输出\(a\)和\(b\)中较小的一个(为什么要输出较小的一个?是因为\(k\le2\times x-1+k\),两个数\(a\)和\(b\)就相当于\(k\)和\(2\times x-1+k\),所以较小的一个就为\(min(a,b)\))。
代码
#include<bits/stdc++.h>
using namespace std;
int T;
long long n;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
if(n%2==1)//n为奇数时直接特判
{
printf("2\n");
continue;
}
else//n为偶数
{
long long a=1,b=0,x=2*n;
while(x%2==0)
{
x/=2;a*=2;//将2*n这个数拆分成奇数乘偶数的形式
}
b=(2*n)/a;
if(min(a,b)<2)printf("-1\n");//a、b的最小值小于2,无解
else if(a<b)printf("%lld\n",a);//输出较小的一个数
else if(a>b)printf("%lld\n",b);
}
}
return 0;
}