# Lightoj Problem-Sum of Consecutive Integers

Explanation:
Let, k be the number of consecutive integers starting
from x whose sum equals N.So we can write,
x+(x+1)+……..+(x+k-1)=N ——–(1)
or, kx+k*(k-1)/2=N
or, 2kx+k^2-k=2N
or, k(2x+k-1)=2N ———-(2)
From equation (2) we can say, k is a divisor of 2N.
Now, from (2)
k(2x+k-1)=2N
or, 2x+k-1=2N/k
or, 2x+k-1=R [Let R=2N/k]
or, 2x=(R-k)+1 ————(3)
From, equation (3) we can say, (R-k) has to be odd number.
Again, since R=2N/k and 2N is even, so R is always even and hence
k must be odd to be (R-k) odd.

From the requirement of problem, x must be positive integers,
so from equation (3) we can write,
R>=k
or, 2N/k>=k
or, 2N>=k^2
or, k<=sqrt(2N) ————(4)

From the above explanation, we can say,
1) k must be a divisor of 2N
2) k must be odd
3) k is less than or equals to the sqaure-root of 2N.

Code

```/*
Problem Tags: Number Theory
Explanation: Let, k be the number of consecutive integers starting
from x whose sum equals N.So we can write,
x+(x+1)+........+(x+k-1)=N --------(1)
or, kx+k*(k-1)/2=N
or, 2kx+k^2-k=2N
or, k(2x+k-1)=2N ----------(2)
From equation (2) we can say, k is a divisor of 2N.
Now, from (2)
k(2x+k-1)=2N
or, 2x+k-1=2N/k
or, 2x+k-1=R  [Let R=2N/k]
or, 2x=(R-k)+1 ------------(3)
From, equation (3) we can say, (R-k) has to be odd number.
Again, since R=2N/k and 2N is even, so R is always even and hence
k must be odd to be (R-k) odd.

From the requirement of problem, x must be positive integers,
so from equation (3) we can write,
R>=k
or, 2N/k>=k
or, 2N>=k^2
or, k<=sqrt(2N) ------------(4)

From the above explanation, we can say,
1) k must be a divisor of 2N
2) k must be odd
3) k is less than or equals to the sqaure-root of 2N.
*/

#include<bits/stdc++.h>
using namespace std;
#define LL long long

bool a[10000009];
int p[500009];
void sieve()
{
LL i,j,k=0; a[0]=1; a[1]=1; p[0]=2;
for(i=3;i<=10000006;i=i+2)
{
if(a[i]==0)
{
p[++k]=i;
for(j=i*i;j<=10000006;j=j+2*i)
a[j]=1;
}
}
}

int main()
{
LL i,j,k,n,m,d,test,t=0;
sieve();
scanf("%lld",&test);
while(test--)
{
scanf("%lld",&n);
LL sq=sqrt(n);
while(n%2==0) n=n/2;
LL ans=1;
for(i=1;p[i]<=sq;i++)
{
if(n%p[i]==0)
{
LL co=0;
while(n%p[i]==0)
{
co++;
n=n/p[i];
}
ans=ans*(co+1);
}
sq=sqrt(n);
}
if(n!=1) ans=ans*2;
printf("Case %lld: %lld\n",++t,ans-1);
}
return 0;
}

```