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

发表于 2019-9-14 18:06

Description求组合数 C ( n , k) 的奇偶性

发表于 2019-9-14 18:06

Input

文件是多case的，每行输入一个 n (1<=n<=10^9)和 k(0<=k<=n) ,当 n 等于 0 且 k 等于 0 时输入结束

发表于 2019-9-14 18:07

Output

对于每一个case，输出一行，为组合数 C ( n , k) 的奇偶性,奇输出1,偶输出0

发表于 2019-9-14 18:07

Sample Input

2 0
2 1
0 0

发表于 2019-9-14 18:07

Sample Output

1
0

发表于 2019-9-14 18:07

题意:求C(n,k)的奇偶性。显然把C(n,k)的值直接求出来进行判断是不可行的。

由于C(n,k)=n!/k!*(n-k)!，要判断奇偶性，即比较分子与分母含有因子2的个数，因此就转化为求n!中含有因子2的个数。

发表于 2019-9-14 18:08

复制

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

}

发表于 2019-9-14 18:08

作者：Matrix海子
　　　　
出处：http://www.cnblogs.com/dolphin0520/
　　　　
本博客中未标明转载的**归作者Matrix海子和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在**页面明显位置给出原文连接，否则保留追究法律责任的权利。

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

相关帖子

浏览过的版块