【哈工大oj】1037 - 组合数末尾的零（位运算，好题）
【哈工大oj】1037 - 组合数末尾的零（位运算，好题）
组合数末尾的零 | ||||||
|---|---|---|---|---|---|---|
Time Limit: 1000 MSMemory Limit: 65536 K Total Submit: 326(169 users)Total Accepted: 207(146 users)Rating: Special Judge: No | Time Limit: 1000 MS | Memory Limit: 65536 K | Total Submit: 326(169 users) | Total Accepted: 207(146 users) | Rating: | Special Judge: No |
Time Limit: 1000 MS | Memory Limit: 65536 K | |||||
Total Submit: 326(169 users) | Total Accepted: 207(146 users) | Rating: | Special Judge: No | |||
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 |
因为m、n范围太大的时候直接计算组合数的时候会溢出。
但二进制有个规律，把其对应的十进制数因数分解后，有多少个2的因子，其二进制末尾就有多少个0，其实很好理解。
那么思路就有了，计算m到m-n+1的每一个数有多少个2的因子，再计算n到1中的数有多少2的因子，相减就是答案了。
代码如下：
#include <stdio.h>
int main()
{
int u;
int a,b; //a中选b个
int t; //二进制
int ans1,ans2,ans;
scanf ("%d",&u);
while (u--)
{
scanf ("%d %d",&a,&b);
ans1=0;
for (int i=a-b+1;i<=a;i++)
{
int t=i;
while (!(t&1))
{
ans1++;
t>>=1;
}
}
ans2=0;
for (int i=b;i>=2;i--)
{
int t=i;
while (!(t&1))
{
ans2++;
t>>=1;
}
}
ans=ans1-ans2;
printf ("%d\n",ans);
}
return 0;
}腾讯云开发者
