https://www.luogu.com.cn/problem/SP22412

Description

求\(n!\)的因子个数，对\(m\)取模。

多组询问

\(n < 10^8, m < 10^9\)

Solution

把\(n!\)分解质因数，考虑一个质数\(p\)的指数，显然为

\(\lfloor n/p \rfloor+ \lfloor n/p^2 \rfloor + \lfloor n/p^3 \rfloor + \cdots\)

答案就是指数+1的乘积。

暴力算复杂度爆炸。

发现对于\(> \sqrt n\)的质数\(p\)，他的指数就是\(\lfloor \frac{n}{p} \rfloor\)，这一部分可以数论分块，即对对分到的一块\([l,r]\)，答案乘上\((\lfloor n/l\rfloor+1)^{pcnt(l,r)}\)（\(pcnt(l,r)\)表示\(l,l+1...r\)里的质数个数）。

线性筛出\(10^8\)以内的质数

小于\(\sqrt n\)的\(p\)直接暴力。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e8+10;
bool vis[N];
ll pcnt[N],pn,ps[N/10];
void shai(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) ps[pn++]=i,pcnt[i]++;
        for(int j=0;j<pn&&i*ps[j]<=n;j++)
        {
            vis[i*ps[j]]=1;
            if(i%ps[j]==0) break;
        }
    }
    for(int i=1;i<=n;i++) pcnt[i]+=pcnt[i-1];
}
inline ll qpow(ll a,ll b,ll m)
{
    ll ans=1%m;
    while(b)
    {
        if(b&1) ans=1ll*ans*a%m;
        a=1ll*a*a%m,b>>=1;
    }
    return ans;
}
int main()
{
    shai((int)1e8);
    int _; scanf("%d",&_); while(_--)
    {
        ll n,m; scanf("%lld%lld",&n,&m);
        ll ans=1,sqn=(ll)sqrt(n);
        for(int i=0;ps[i]<=sqn;i++)
        {
            ll tmp=0,p=ps[i];
            while (p<=n) tmp=(tmp+n/p)%m,p*=ps[i];
            ans=1ll*ans*(tmp+1)%m;
        }
        for(ll l=sqn+1,r=0;l<=n;l=r+1)
        {
            r=n/(n/l);
            ans=1ll*ans*qpow(n/l+1,pcnt[r]-pcnt[l-1],m)%m;
        }
        printf("%lld\n",ans);
    }
    return 0;
}