HLP_RAMS

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 = (n₀ C r₀ % m) * (n₁ C r₁ % m)*........

(n_k C r_k % m), where n<₀n₁...n_k and r₀r₁...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;
}