csu-1021-组合数末尾的零

文章目录

• 一、问题描述
• 二、代码

一、问题描述

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

1

6

二、代码

代码如下（示例）：

include

using namespace std;

int main()

{

int t;

cin>>t;

while(t–)

{

int m,n,i=0,s=1,sum1=0,sum2=0;

cin>>m>>n;

if(mn)

{

cout<<“0”<<endl;

}

else

{

for(i=m-n+1;i<=m;i++)

{

s=i;

while(s>1)

{

if(s&1||s0)

break;

sum1++;

s>>=1;

}

}

for(i=1;i<=n;i++)

{

s=i;

while(s>1)

{

if(s&1||s==0)

break;

sum2++;

s>>=1;

}

}

cout<<sum1-sum2<<endl;

}

}

return 0;

}