|
5啊哈币
本帖最后由 hsjr1200 于 2013-4-9 11:17 编辑
题目:
Problem Description
从m个不同元素中取出n (n ≤ m)个元素的所有组合的个数,叫做从m个不同元素中取出n个元素的组合数。组合数的计算公式如下:
C(m, n) = m!/((m - n)!n!)
现在请问,如果将组合数C(m, n)写成二进制数,请问转这个二进制数末尾有多少个零。
Input
第一行是测试样例的个数T,接下来是T个测试样例,每个测试样例占一行,有两个数,依次是m和n,其中m ≤ n ≤ 1000。
Output
分别输出每一个组合数转换成二进制数后末尾零的数量。
Sample Input
2
4 2
1000 500
Sample Output
1
6
上面的意思是,输入2行,输入4 2得 1,输入1000 500 得6.
我写的程序,会超时的。
#include <stdio.h>
int main(int argc, char *argv[])
{int a,b,m,n,i,t,k,j;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&a,&b);
t=0;k=0;
if((b+1)%2==0)
{
for(i=b+1;i<=a;i=i+2)
{ m=i;
while(m%2==0)
{
t+=1;
m=m/2;
}
continue;
}
}
if((b+1)%2!=0)
{
for(i=b+2;i<=a;i=i+2)
{ m=i;
while(m%2==0)
{
t+=1;
m=m/2;
}
continue;
}
}if(a-b<2)
{
t=0;
}
if(a-b>=2)
{
for(i=2;i<=a-b;i=i+2)
{ n=i;
while(n%2==0)
{
k+=1;
n=n/2;
}
continue;
}
} printf("%d\n",t-k);}
}
|
|