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