Hust oj 1037 组合数末尾的零(组合数）

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

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

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

第一行是测试样例的个数T，接下来是T个测试样例，每个测试样例占一行，有两个数，依次是m和n，其中m ≤n ≤ 1000。

分别输出每一个组合数转换成二进制数后末尾零的数量。

2

4 2

1000 500

1

6

这题是求组合数末尾的0，因为C（M，N）= M！ / （M - N）！* N！，而且我们知道如果一个十进制数转化二进制数时末尾想要出现0的话，必然是2^N,且有N个0，因为可以被除N次，所以求出分母分子中2的倍数求出来，相接就是结果

#include<cstdio>
#include<iostream>
using namespace std;int t;
int n,m;
const int maxn = 1005;
int a[maxn];int c(int m,int n)
{int ans1 = 0;int ans2 = 0;for(int i=m;i>=(m-n+1);i--){int flag1 = i;while(flag1 % 2 == 0){ans1++;flag1 /= 2;}}for(int i=n;i>=1;i--){int flag2 = i;while(flag2 % 2 == 0){ans2++;flag2 /= 2;}}return ans1 - ans2;
}
int main()
{scanf("%d",&t);while(t--){scanf("%d%d",&m,&n);printf("%d\n",c(m,n));}return 0;
}