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;
}
No comments:
Post a Comment