Lightoj Problem-Sum of Consecutive Integers

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;
}

Advertisements
About

ACM Competitive Programmer

Posted in Lightoj, Math, Number Theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: