PKU 3219-Binomial Coefficients

問題概要

0<=k<=n<2^31について、nCkの偶奇判定をせよ

解法

nCk=n!/k!/(n-k)!なので、整数m!に含まれる素因数2の個数を求めることが出来れば簡単に判定出来る。
これは、mをどんどん2で割っていくことで求めることが出来る。

実装(C)

#include <stdio.h>
int calc_2(int a){
  int res=0;
  a>>=1;
  while(a>0){
    res+=a;
    a>>=1;
  }
  return res;
}
int n,k;
int main(){
  while(~scanf("%d%d",&n,&k)){
    if(calc_2(n)-calc_2(k)-calc_2(n-k)>0){
      puts("0");
    }else{
      puts("1");
    }
  }
}