题意 （Codeforces 546D）

给定一个数x=a!b!x=a!b!的形式，问其中有几个质因数。

分析

数据规模略大，故先作预处理。预处理的时候运用了前缀和和记忆化搜索的思想。

之后就比较简单了。

代码

#include 
    
     #define MP make_pair#define PB push_back#define fi first#define se second#define ZERO(x) memset((x), 0, sizeof(x))#define ALL(x) (x).begin(),(x).end()#define rep(i, a, b) for (int i = (a); i <= (b); ++i)#define per(i, a, b) for (int i = (a); i >= (b); --i)#define QUICKIO                  \    ios::sync_with_stdio(false); \    cin.tie(0);                  \    cout.tie(0);using namespace std;using ll = long long;using ull = unsigned long long;using pi = pair
     
      ;const int MAXN=5000000;bool isPrime[MAXN+5];ll cnt[MAXN+5];ll getCnt(int x){    if(cnt[x]!=-1) return cnt[x];    else    {        if(isPrime[x]) return cnt[x]=1;        for(int i=2;i*i<=x;++i)        {            if(isPrime[i] && x%i==0) return cnt[x]=getCnt(x/i)+1;        }    }}ll sum[MAXN+5];int main(){QUICKIO    memset(isPrime,true,sizeof(isPrime));    ZERO(sum);    isPrime[0]=isPrime[1]=false;    rep(i,2,MAXN)    {        if(isPrime[i])        {            for(int j=i*2;j<=MAXN;j+=i)                isPrime[j]=false;        }    }    memset(cnt,-1,sizeof(cnt));    cnt[1]=0;    rep(i,1,MAXN)    {        sum[i]=sum[i-1]+getCnt(i);        //cout<
      
       <