Description
从m个不同元素中取出n (n ≤ m)个元素的所有组合的个数,叫做从m个不同元素中取出n个元素的组合数。组合数的计算公式如下:
C(m, n) = m!/((m - n)!n!)
现在请问,如果将组合数C(m, n)写成二进制数,请问转这个二进制数末尾有多少个零。
Input
第一行是测试样例的个数T,接下来是T个测试样例,每个测试样例占一行,有两个数,依次是m和n,其中n ≤ m ≤ 1000。
Output
分别输出每一个组合数转换成二进制数后末尾零的数量。
Sample Input
2 4 2 1000 500
Sample Output
16
思路:将组合数的分子分母中所有2的因子分离出来,那么相除的结果中剩余的2的因子,也就是组合数2的因子,即末尾0的个数、
#include<stdio.h>
int find(int x)
{
int cnt = 0;
for (int i = 1; i <= x; i++){
int n = i;
while (n)
{
if (n & 1)break;
n >>= 1;
cnt++;
}
}
return cnt;
}
int main()
{
int T;
while (~scanf("%d", &T))
{
int x, y;
while (T--)
{
scanf("%d%d", &x, &y);
printf("%d\n", find(x) - find(x - y) - find(y));
} } return 0;
}
/**********************************************************************
Problem: 1021
User: leo6033
Language: C++
Result: AC
Time:4 ms
Memory:1120 kb
**********************************************************************/