csu1021: 组合数末尾的零

C(m, n) = m!/((m - n)!n!)

将组合数C(m, n)写成二进制数，这个二进制数末尾有多少个零?

* 自然数可以进行质因数分解，质因子2的指数即相应二进制末尾零的个数；

将各个数二进制末尾0的个数累加，得到阶乘数末尾0的个数。

优化：

# include <stdio.h>
int f[] = {0,1,3,7,15,31,63,127,255,511};
int main(){
    int T, m, n, i, ans;
    scanf("%d", &T);
    while (T-- > 0){
        ans = 0;
        scanf("%d%d", &m, &n);
        for(i=0; i<10; ++i){
            if (m>>i & 0x1)ans += f[i];
            if (n>>i & 0x1)ans -= f[i];
            if ((m-n)>>i & 0x1)ans -= f[i];
        }
        printf("%d\n", ans);
    }
    return 0;
}

更新：2012/3/12

又翻了翻编程之美，看到一个求 N 的阶乘末尾 0 的个数是转化成：N - N 的二进制表示中 1 的个数；

组合数可以化为阶乘相除的形式；

而正整数 N 的二进制表示中 1 的个数可以用 log2(N) 的方法得到，于是有了下面的：

 1 /*csu 1021*/
 2 # include <stdio.h>
 3 
 4 int cnt(int n);
 5 
 6 int main()
 7 {
 8     int T, m, n;
 9     
10     scanf("%d", &T);
11     while (T-- && scanf("%d%d", &m, &n))
12           printf("%d\n", cnt(m-n)+cnt(n)-cnt(m)); // 稍作计算得到 
13     
14     return 0;
15 }
16 
17 int cnt(int n)
18 {
19     int c = 0;
20     while (n)
21     {
22           n &= (n-1);
23           ++c;      
24     }
25     return c;
26 }

相比之前加表的方法各有千秋。。OJ显示的耗时都是16ms。