排列与二进制（暑假每日一题 33）

在组合数学中，我们学过排列数。

从 $n$ 个不同元素中取出 $m（m<=n）$个元素的所有排列的个数，叫做从 $n$ 中取 $m$ 的排列数，记为 $p(n,m)$。

具体计算方法为 $p(n,m)=n(n-1)(n-2)\dots \dots (n-m+1)=n!/(n-m)!$（规定 $0!=1$）。

当 $n$ 和 $m$ 不是很小时，这个排列数是比较大的数值，比如 $p(10,5)=30240$。

如果用二进制表示为 $p(10,5)=30240=(111011000100000{)}_b$，也就是说，最后面有 $5$ 个零。

我们的问题就是，给定一个排列数，算出其二进制表示的后面有多少个连续的零。

输入格式
输入包含多组测试数据。

每组数据占一行，包含两个整数 $n,m$。

最后一行为 0 0，表示输入结束，无需处理。

输出格式
每组数据输出一行，一个结果，表示排列数 $p(n,m)$ 的二进制表示后面有多少个连续的零。

数据范围
$1\le m\le n\le 10000,$
输入最多包含 $100$ 组数据。

输入样例：

10 5
6 1
0 0
1
2
3

输出样例：

5
1
1
2

---

• $10$ 进制时，要求数的右边有几个$0$，就是求数有几个因子$10$
  同理二进制就是求数有几个因子 $2$

• 如何求 $n!$ 中有几个因子 $p$？
  $n!=n\ast (n-1)\ast (n-2)\ast ...\ast 1$
  等价于求 $n/p+n/p^2+..+n/p^k$
  $n/p$ 求的是 $1n$ 中能被 $p$ 整除的数的个数
  $n/p^2$ 求的是 $1n$ 中能被 $p^2$ 整除的数的个数
  而能被p^2整除的数 包含有 $2$ 个 $p$ 的因子
  但是这些数也是 $p$ 的倍数，所以在 $n/p$ 时已经加了一遍
  此时只需要 $+n/p^2$ 即可。
  其它的同理

#include

using namespace std;

int f(int n, int p){
    
    int res = 0;
    while(n) res += n / p, n /= p;
    return res;
}

int main(){
    
    int n, m;
    while(cin >> n >> m, n)
        cout << f(n, 2) - f(n - m, 2) << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19