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