CSU 1021——組合數末尾的零、HRBUST 1037——組合數末尾的零【水題】

​​題目傳送門​​

Description

從m個不同元素中取出個元素的所有組合的個數，叫做從m個不同元素中取出n個元素的組合數。組合數的計算公式如下:

現在請問，如果将組合數寫成二進制數，請問轉這個二進制數末尾有多少個零。

Input

第一行是測試樣例的個數T，接下來是T個測試樣例，每個測試樣例占一行，有兩個數，依次是m和n，其中。

Output

分别輸出每一個組合數轉換成二進制數後末尾零的數量。

Sample Input

Sample Output

題解

• 末尾的可以用位運算搞出來
• 乘法和除法操作之後，末尾的實際上就是加減的關系，求階乘的時候，直接把每個乘數末尾的得到之後相加會快一些

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;
}