C(n,k)
Description
求组合数 C ( n , k) 的奇偶性Input
文件是多case的，每行输入一个 n (1<=n<=10^9)和 k(0<=k<=n) ,当 n 等于 0 且 k 等于 0 时输入结束Output
对于每一个case，输出一行，为组合数 C ( n , k) 的奇偶性,奇输出1,偶输出0Sample Input
2 0 2 1 0 0Sample Output
1 0
题意:求C(n,k)的奇偶性。显然把C(n,k)的值直接求出来进行判断是不可行的。
由于C(n,k)=n!/k!*(n-k)!，要判断奇偶性，即比较分子与分母含有因子2的个数，因此就转化为求n!中含有因子2的个数。
#include < iostream >
using namespace std;
int count( int n)
{
int num = 0 ;
while (n)
{
num += n / 2 ;
n = n / 2 ;
}
return num;
}
int main( void )
{
int n,k;
while (scanf( " %d%d " , & n, & k) == 2 &&! (n == 0 && k == 0 ))
{
int a,b,c;
a = count(n);
b = count(k);
c = count(n - k);
if (a > b + c)
printf( " 0\n " );
else
printf( " 1\n " );
}
return 0 ;
}
