3219:Binomial Coefficients

keyword

二項係数　C++　約数

概要

二項係数(n,k)(k,n<2^31)が2で割りきれるかどうかを求める問題。
階乗使った方の定義で、分子と分母が約数に2をいくつ含めるか求めればよい。2のべきで割り算するだけ。

int main(){
    int n, k, i, j, cnt;

    while(scanf("%d%d",&n,&k)!=EOF){
        cnt = 0;
        for(i=1;i<=31;i++) cnt+= (n>>i) - ((n-k)>>i) - (k>>i);
        printf("%d\n",cnt>0?0:1);
    }

    return 0;
}