【题解】传递组合数

题意

给你一个组合数，下面进行游戏，牛牛作为第一个人，选择一个，要求且整除，并将传给下一个人。若当前人手上的数字等于了，游戏则结束，问最多能让多少个人参与进来。

题解

考虑最多的人参与进来的话就需要每次的尽量要小，所以取组合数的质因子就好了，也就是问题转化为了求组合数有多少个质因子。由于组合数实际上是阶乘的乘除，那么质因子的个数也就是阶乘质因子的加减了。那么可以考虑预处理阶乘的质因子。考虑每个质数作为因子的贡献，在将质数筛出来的同时存入数组中。

    for(int i=2;i<N;i++)
    {
        if(dp[i]==0)
        {
            for(int j=i;j<N;j+=i)//考虑每个i的倍数j,j里面含有的i的个数是j/i+1
            {
                dp[j]=dp[j/i]+1;
            }
        }
    }

处理完每个数的质因子的个数之后，可以求一个前缀和就是阶乘的质因子了。
那么最后的答案就是

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int dp[N];
int main()
{
    memset(dp,0,sizeof(dp));
    for(int i=2;i<N;i++)
    {
        if(dp[i]==0)
        {
            for(int j=i;j<N;j+=i)
            {
                dp[j]=dp[j/i]+1;
            }
        }
    }
    for(int i=1;i<N;i++)
        dp[i]+=dp[i-1];
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        printf("%d\n",dp[n]-dp[m]-dp[n-m]+1);
    }
    return 0;
}