Thursday, 30 July 2015

HLP_RAMS

Standard

Topper Rama Rao

Link to the question : HLP_RAMS 

HINT :

To find whether nCr is odd or even we use the lucas theorem. 
Lucas theorem states that nCr % m, where, m is a prime number = (n0 C r0 % m) * (n1 C r1 % m)*........
(nk C rk % m), where n<0n1...nk and r0r1...rk are the representation of n and r in base m respectively. Hence, in base 2 representation, the digits will be either 0 or 1. 
So,according to lucas theorem,  nCr % 2 will give us the cases 1C1, 1C0, 0C0, 0C1. Now, 0C1  = 0. Hence, if nCr has the case 0C1 then its always even else odd. 
Now for counting the number of odd terms we count the number of 1's in n' s binary representation. We can assign either 0 or 1 to the 1's of n in nCr. Hence, number off odd terms = 2^(no of 1's).

SOURCE CODE :

/* Topper Rama Rao */
/* Sushant Gupta */
#include<stdio.h>
#include<math.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long int n,i,odd,x,c=0;;
        scanf("%lld",&n);
        x=n;
        if(n==0)
            printf("0 1\n");
        else
        {
            while(n>0) {
                if(n&1==1)
                    c++;
               n=  n>>1;
            }
            odd = pow(2,c);
            printf("%lld %lld\n",x+1-odd,odd);


        }


    }
    return 0;
}

0 comments:

Post a Comment