数论是我一生之敌。QAQ

这个巨佬的博客数论是极好的，但是，他好像弃坑了。

欧拉筛

emmm，这个比较简单，就贴代码。

for (i=2; i<maxn; ++i) { if (!isn_prime[i]) prime[++cnt]=i; for (phi[i]=cnt,j=1; j<=cnt&&prime[j]*i<maxn; ++j) { isn_prime[i*prime[j]]=1; if (i%prime[j]==0) break; } }

扩欧求逆元

推导

老是会忘掉。qwq

$ax+by=gcd(a,b)=1$

$\because gcd(a,b)=gcd(b,a\%b)$

$\therefore ax+by=gcd(a,b)=gcd(b,a\%b)=b{x}^{\prime }+(a\%b)y^{\prime }$

$\Rightarrow b{x}^{\prime }+(a-b\ast \lfloor \frac{a}{b}\rfloor )y^{\prime }$

$\Rightarrow a{y}^{\prime }+b(x^{\prime }-y^{\prime }\ast \lfloor \frac{a}{b}\rfloor )$

$\therefore x=y^{\prime },y=(x^{\prime }-y^{\prime }\ast \lfloor \frac{a}{b}\rfloor )$

代码

int ex_gcd(int a,int b,int &x,int &y) { if (b==0) return x=1,y=0,a; int ans=ex_gcd(b,a%b,x,y); int tmp=x; x=y,y=tmp-a/b*y; return ans; }

线性求逆元

$inv[a]=inv[P\%a]\ast (P-\lfloor \frac{P}{a}\rfloor )$

证明

令 $x=P\%a,y=\lfloor \frac{P}{a}\rfloor$

则 $x+ay=P$

即 $x+ay\equiv 0(modP)$

$x\equiv -ay(modP)$

$inv(a)\equiv inv(x)\ast (P-y)(modP)$

$\therefore inv(a)\equiv inv(P\%a)\ast (P-\lfloor \frac{P}{a}\rfloor )$

代码

for (inv[1]=1,i=2; i<maxn&&i<P; ++i) inv[i]=1ll*inv[P%i]*(P-P/i)%P;

例题

SDOI2008 沙拉公主的困惑

思路

我好弱，FTQ说这种题很经典，我却没做过。QwQ

我们可以吧$N!$分成长$M!$块，显然每块答案是$\varphi (M!)$

所以$ans=\frac{N!}{M!}\ast \phi (M!)$

可以知道对于$\phi (N)$有

$\phi (N)=\phi ({\prod }_1^m{P}_i^{{\epsilon }_i})={\prod }_i^m(P_i^{{\epsilon }_i}\ast \frac{P_i-1}{P_i})=N\ast {\prod }_i^m(\frac{P_i-1}{P_i})$

所以$ans=N!\ast \prod (P-1)\ast \prod inv(P)$ P为小于等于$M$的质数。

代码

#include<cstdio> #include<string> const int maxn=1e7+5; bool isn_prime[maxn]; int N,M,T,P,cnt; int prime[maxn],phi[maxn]; int inv[maxn],fac[maxn]; int fac_prime[maxn],fac_inv_prime[maxn]; void init() { register int i,j; for (i=2; i<maxn; ++i) { if (!isn_prime[i]) prime[++cnt]=i; for (phi[i]=cnt,j=1; j<=cnt&&prime[j]*i<maxn; ++j) { isn_prime[i*prime[j]]=1; if (i%prime[j]==0) break; } } for (inv[1]=1,i=2; i<maxn&&i<P; ++i) inv[i]=1ll*inv[P%i]*(P-P/i)%P; for (fac_prime[0]=i=1; i<=cnt; ++i) fac_prime[i]=1ll*fac_prime[i-1]*(prime[i]-1)%P; for (fac_inv_prime[0]=i=1; i<=cnt; ++i) if (prime[i]==P) fac_inv_prime[i]=fac_inv_prime[i-1]; else fac_inv_prime[i]=1ll*fac_inv_prime[i-1]*inv[prime[i]%P]%P; for (fac[0]=i=1; i<maxn; ++i) if (i!=P) fac[i]=1ll*fac[i-1]*i%P;else fac[i]=fac[i-1]; } int main() { scanf("%d%d",&T,&P),init(); while (T--) { scanf("%d%d",&N,&M); if (N>=P&&M<P) puts("0");else printf("%lld\n",1ll*fac[N]*fac_prime[phi[M]]%P*fac_inv_prime[phi[M]]%P); } return 0; }