洛谷 P2155 [SDOI2008]沙拉公主的困惑

传送门:https://www.luogu.com.cn/problem/P2155

题目大意

• 求 \(1 , 2 , …… , n !\) 中，与 \(m !\) 互质的数的个数
  
  

Solution

• 对于上述问题，我们可以转换为求：在 \(1 , …… , n !\) 中，不含小于 \(m\) 的质数为因子的数的个数
  
  （即:设 \(p_1 , p_2 , …… , p_k\) 为不大于 \(M\) 的质数，求在 \(1 , …… , n!\) 中，不包含因子 \(p_1 , p_2 , …… , p_k\) 的数的个数）
  
  

• 则我们可以将 \(1\) 到 \(n!\) 分为若干段长度为 \(m!\) 的数列，其中的每一段中与 \(m!\) 互质的数的个数等于 \(1\) 到 \(m!\) 中与 \(m!\) 互质的数的个数
  
  那么，我们可以获得如下式子：\(ans = \frac{n!}{m!} \times \varphi{(m!)}\) ，而 \(\varphi{(m!)} = m! \times \frac{\prod{(p_i-1)}}{\prod{p_i}}\)
  
  则上述公式可以转换为：\(ans = n! \times \frac{\prod{(p_i-1)}}{\prod{p_i}}\)

• 则我们可以在线性时间内将 \(n!\) 、\(\prod{p_i-1}\) 、\(\prod{p_i}\)预处理得到，在每次询问时直接 \(O(1)\) 查询 \(n!\) 和 \(\prod{p_i-1}\) ，再用费马小定理结合快速幂求得 \(\prod{p_i}\) 的逆元，相乘即可

Code

#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;

const ll maxn=10000010;
ll t,r,n,m,tot;
ll jie[maxn],f1[maxn],f2[maxn],prime[maxn];
bool vis[maxn];

void Init(ll x){ \\线性筛
	memset(vis,true,sizeof(vis));
	vis[0] = vis[1] = false;
	for(int i = 2;i <= x;i++){
		if(vis[i])
			prime[++tot] = i;
		for(int j = 1;j <= tot && i * prime[j] <=x ;j++){
			vis[i * prime[j]] = false;
			if(i % prime[j] == 0)
			    break;
		}
	}
}
inline ll ksm(ll a,ll b,ll p)\\快速幂求逆元
{
    ll ret=1;
    while(b)
    {
        if(b&1) ret=ret*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ret;
}

int main(void)
{
    scanf("%lld%lld",&t,&r);

    Init(maxn-5);
    jie[1]=f1[1]=f2[1]=1;

    for(int i=2;i<=maxn-5;i++) \\预处理
    {
        jie[i]=jie[i-1]*i%r;

        if(vis[i])
        {
            f1[i]=f1[i-1]*(i-1)%r; 
            f2[i]=f2[i-1]*i%r;
        }
        else
        {
            f1[i]=f1[i-1];
            f2[i]=f2[i-1];
        }
    }

    while(t--)
    {
        scanf("%lld%lld",&n,&m);

        printf("%lld\n",(jie[n]*f1[m]%r)*ksm(f2[m],r-2,r)%r);
    }

    return 0;
}