正題

題目鏈接:
https://www.lydsy.com/JudgeOnline/problem.php?id=2186
https://www.luogu.org/problem/P2155

---

題目大意

求$$\sum _{i=1}^{n!}((i,m!)==1)$$

---

解題思路

因為$gcd(m!,i)=1?gcd(m!,i+m!)=1$所以這個互質(zhì)的個數(shù)是一循環(huán)節(jié)。而又因為$n\ge m$所以答案就是
$$\frac{n!}{m!}\phi (m!)$$
而因為$m!$質(zhì)因數(shù)分解后是包括$1～m$里的所有素數(shù)所以有
$$?\frac{n!}{m!}m!\prod _{i=1}^k\frac{p_i?1}{p_i}$$
$$n!\prod _{i=1}^k\frac{p_i?1}{p_i}$$
線性篩素數(shù)+線性推逆元預(yù)處理即可

時間復(fù)雜度$O(m+T)$

---

$code$

#pragma GCC optimize(2) %:pragma GCC optimize(3) #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=10000000; int n,m,cnt,prime[N+10],inv[N+10]; int Phi[N+10],Phinv[N+10],Fac[N+10],pos[N+10],p,T; bool v[N+10]; int main() {v[1]=1;scanf("%d%d",&T,&p);for(int i=2;i<=N;i++){pos[i]=pos[i-1];if(!v[i]) prime[++cnt]=i,pos[i]++;for(int j=1;j<=cnt&&i*prime[j]<=N;j++){v[prime[j]*i]=1;if(!(i%prime[j])) break;}}inv[1]=Phi[0]=Phinv[0]=Fac[1]=1;for(int i=2;i<=N;i++){inv[i]=(long long)(p-p/i)*inv[p%i]%p;Fac[i]=(long long)Fac[i-1]*i%p;}for(int i=1;i<=cnt;i++){Phi[i]=(long long)Phi[i-1]*(prime[i]-1)%p;Phinv[i]=(long long)Phinv[i-1]*inv[prime[i]]%p;}while(T--){scanf("%d%d",&n,&m);printf("%d\n",(long long)Fac[n]*Phi[pos[m]]%p*Phinv[pos[m]]%p);} }

總結(jié)

以上是生活随笔為你收集整理的bzoj2186,P2155-[SDOI2008]沙拉公主的困惑【线性筛,欧拉函数,逆元】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。