<<点个赞吧

$\huge\color{Gold}{暑假每日一题2022}\color{black}{题解集合}$

算法

$模拟$

分析

这题需要找一下规律
这个可能有点难发现

不过没事，我们先从样例入手

先来看$10$和$5$这个样例
根据题目告诉你的求$p(n,m)$的公式：$p(n,m)=n(n−1)(n−2)……(n−m+1)=n!/(n−m)!$，$p(10,5)$就等于 $10 *9 * 8 * 7 * 6 $
我们再求出这五个数的二进制表示：$(1010)_2,(1001)_2,(1000)_2,(111)_2,(110)_2$
很巧，这五个数的二进制表示下的末尾的$0$的总数刚好是$5$

好家伙，这不就出来了吗？！

再试几个别的数据也是如此

具体证明过程读者可以思考思考~

$\ \ $

这样一来，程序的实现就很简单了
我们只需要计算$p(n,m)$中每个$n,n-1,n-2……n-m+1$最多能被$2$整除多少次，然后把每个$n,n-1,n-2……n-m+1$能被$2$整除的次数加起来就行了

如果觉得我表述的不太清楚的可以自己看程序再理解理解

C++ 代码

#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
int n,m;
int f(int x){
    int res=0;
    while(x%2==0){
        res++;
        x/=2;
    }
    return res;
}
int main(){
    while(cin>>n>>m&&n){
        int ans=0;
        for(int i=n;i>=n-m+1;i--) ans+=f(i);
        printf("%d\n",ans);
    }
    return 0;
}