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,偶输出0 Sample Input
2 0 2 1 0 0 Sample 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 ; } http://www.cnblogs.com/dolphin0520/archive/2011/04/12/2014026.html