组合数末尾的零

题目连接：http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=30303

题意：

      从m个不同元素中取出n (n ≤ m)个元素的所有组合的个数，叫做从m个不同元素中取出n个元素的组合数。组合数的计算公式如下:

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

      现在请问，如果将组合数C(m, n)写成二进制数，请问转这个二进制数末尾有多少个零。

       案例：

      input:

      2

      4 2

      1000 500

      output:

      1

      6

思路分析：

      因为n ≤ m≤1000，所以m！的结果过大会溢出，所以先得出组合数再化为二进制的方法是行不通的。因此需要逐个计算。

      进行简单归类后会发现，当某个数可以有多少个因子是2，它的二进制末尾就有多少个0；因此在循环计算组合时可以逐个求出可以有多少因子是2 。

      先将才组合数的计算公式化简，可得结果为n+1到m的乘积除以1到m-n的乘积，再对分母进行循环求出可以有多少因子是2，得出a，同时对分子也进行循环求出可以有多少因子是2，

      得出b，最后用分母的因字数减去分子的因字数，输出a-b。

源代码如下：

     

#include<iostream>
using namespace std;
int main()
{
    int m,n,a,T,j,i,b,k;
    cin>>T;
    for(i=0;i<T;i++)
    {
        a=0;b=0;
        cin>>m>>n;
        for(j=n+1;j<=m;j++)
        {
            k=j;
            while(k%2==0)
            {
                k=k/2;
                a++;
            }
        }
        for(j=1;j<=m-n;j++)
        {
            k=j;
            while(k%2==0)
            {
                k=k/2;
                b++;
            }
        }
        cout<<a-b<<endl;
    }
    return 0;
}