判断C(n,k)的奇偶性 soj2668

时间：2011-04-12 来源：海子

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