light oj 1278 链接http://lightoj.com/volume_showproblem.php?problem=1278
只想说，是抄的
题意:给定n,求n可以写成多少种至少两个连续正整数的和的形式。
思路：设n可以写成a,a+1,a+2……a+k-1的和(其中a>=1)，即n=(a+a+k-1)*k/2。若k为奇数，那么n=(a+(k-1)/2)*k，若k为偶数，那么(a+a+k-1)为奇数。所以若有一组解，那么必对应一个奇素数。下面证明，对于一个除1以外的奇素数，每个奇素数都对应一个解。设x为n的一个奇素数，令y=n/x。那么x与y的关系只有下面两种：
（1）y>(x-1)/2，此时，n必定能写成n=(a+(k-1)/2)*k的形式。其中，x=k,y=a+(k-1)/2，此时满足a=y-(k-1)/2=y-(x-1)/2为正整数；
（2）y<=(x-1)/2，此时n必定能写成n=n=(a+a+k-1)*k/2的形式。其中，y=k/2,x=a+a+k-1,此时a=(x+1-k)/2=(x+1-y*2)/2=(x-1)/2-y+1>=1。
因此，一个奇素数必对应一个解。
#include<stdio.h>
#define i64 long long
const int MAX=10000005;
bool tag[MAX];
int prim[670000],cnt;
i64 n;
void init()
{
int i,j;
for(i=2;i<MAX;i++) if(!tag[i])
{
prim[++cnt]=i;
for(j=i*2;j<MAX;j+=i) tag[j]=1;
}
}
i64 Deal()
{
i64 t,i,ans=1;
for(i=1;i<=cnt && (i64)prim[i]*prim[i]<=n;i++) if(n%prim[i]==0)
{
t=0;
while(n%prim[i]==0)
{
t++;
n/=prim[i];
}
if(prim[i]&1) ans*=(t+1);
}
if(n>1 && (n&1)) ans*=2;
return ans-1;
}
int main()
{
init();
int T,i;
scanf("%d",&T);
for(i=1;i<=T;i++)
{
scanf("%lld",&n);
printf("Case %d: %lld\n",i,Deal());
}
return 0;
}
