【GDOI2017模拟8.14】佐助的难题

Description

给出n和m，求n!的范围中与m!互质的数的个数。答案对r取模。 n,m<=1e7，r>n>=m，且r为质数。

Solution

首先，如果gcd(a,b)=1，那么gcd(a+b,b)=1. 所以，1~km与m互质的数的个数为 k∗φ(m) 答案就是

n!m!φ(m!) 然后， φ(m!)=m!∏p<=n且p为质数p−1p Ans=n!∏p<=n且p为质数p−1p O(n)线筛出范围内的所有质数和它们的逆元，顺便预处理阶乘就可以了。 Ps:逆元有线性求法。

Code

#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define N 10000000 using namespace std; typedef long long ll; int ty,n,m,bz[N+5],p[N],mo,fact[N+5],inv[N+5],ans[N+5]; void exgcd(int a,int b,int &x,int &y) { if (!b) {x=1;y=0;return;} int xx,yy;exgcd(b,a%b,xx,yy); x=yy;y=xx-a/b*yy; } int main() { scanf("%d%d",&ty,&mo);fact[1]=ans[1]=1; fo(i,2,N) { fact[i]=(ll)fact[i-1]*i%mo;int y; if (!bz[i]) { p[++p[0]]=i;exgcd(i,mo,inv[i],y); inv[i]=(inv[i]%mo+mo)%mo; } fo(j,1,p[0]) { int k=i*p[j];if (k>N) break; bz[k]=1;if (!(i%p[j])) break; } } fo(i,2,N) { ans[i]=ans[i-1]; if (!bz[i]&&i!=mo) ans[i]=(ll)ans[i]*(i-1)%mo*inv[i]%mo; } for(;ty;ty--) scanf("%d%d",&n,&m),printf("%d\n",(ll)fact[n]*ans[m]%mo); }