CSU 1021——组合数末尾的零、HRBUST 1037——组合数末尾的零【水题】

题目传送门

Description

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

$C(m,n)=m!/((m?n)!n!)$

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

Input

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

Output

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

Sample Input

2
4 2
1000 500

Sample Output

1
6

题解

• 末尾的$0$可以用位运算搞出来
• 乘法和除法操作之后，末尾的$0$实际上就是加减的关系，求阶乘的时候，直接把每个乘数末尾的$0$得到之后相加会快一些

AC-Code

#include <bits/stdc++.h>
using namespace std;const int maxn = 300;
const int mod = 1e9;int solve(int n) {
    int sum = 0;for (int i = 1; i <= n; ++i) {
    int num = 0;int x = i;while (!(x & 1)) {
    x >>= 1;++num;}sum += num;}return sum;
}int main() {
    int T;cin >> T;while (T--) {
    int m, n;cin >> m >> n;cout << solve(m) - solve(m - n) - solve(n) << endl;}return 0;
}