LightOJ 1278 Sum of Consecutive Integers数论

我可算发现了数论啊~就是导啊导啊~~

设n可以写成a,a+1,a+2……a+k-1的和(其中a>=1)，即n=(a+a+k-1)*k/2。那么2a-1=2n/k-k。所以2n/k-k为奇数（分析一下发现k为偶数与题设矛盾）n的一个奇素因子对应一个解，这么想来，素因子这玩意只有2 是偶数，那么根据a=p1^r1*p1^r2*p3^r3……pk^rk n的因子的排列组合就是(p1+1)*(p2+1)*.....*(pk+1)当然了，最后积得-1（本身不算）

Description

Given an integer N, you have to find the number of ways you can express N as sum of consecutive integers. You have to use at least two integers.

For example, N = 15 has three solutions, (1+2+3+4+5), (4+5+6), (7+8).

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing an integer N (1 ≤ N ≤ 10¹⁴).

Output

For each case, print the case number and the number of ways to express N as sum of consecutive integers.

Sample Input

828495

Sample Output

Case 1: 1

Case 2: 3

Case 3: 1

Case 4: 2

Case 5: 47

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=10000005;
bool isnotprime[N];
int t;
int prime[670000];
long long num;
long long m,sum;
int main()
{
    memset(isnotprime,false,sizeof(isnotprime));
    isnotprime[0]=true,isnotprime[1]=true;
    int k=0;
    for(int i=2;i<N;i++)
    {
         if(!isnotprime[i])
          prime[k++]=i;
          for(int j=0;prime[j]*i<N&&j<k;j++)
          {
               isnotprime[i*prime[j]]=true;
               if(!(i%prime[j])) break;
          }//终于理解素数筛这种方法是把i既用来遍历1~N又用来与原来的第j个素数相乘以筛合数
    }
    //for(int i=0;i<10;i++) printf("%d ",prime[i]);
    //freopen("cin.txt","r",stdin);

    while(~scanf("%d",&t))
    {
         int cnt=1;
         while(t--)
         {
              scanf("%lld",&m);
              sum=1;
              while(m%2==0) m/=2;
              for(int i=0;(long long)prime[i]*prime[i]<=m&&i<k;i++)
               if(m%prime[i]==0)
              {
                   num=0;
                   while(m%prime[i]==0)
                   {
                        m/=prime[i];
                        num++;
                   }
                   sum*=(num+1);
              }
              if(m>1&&(m&1)) {sum*=2; }
              sum--;
              printf("Case %d: %lld\n",cnt++,sum);
         }
    }
    return 0;
}