Problem Link: Here
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; }