【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=2186
【题意】
若干个询问，求1..n!中与m!互质的个数。
【思路】
首先有gcd(a,b)=gcd(a+b,b)，则一个与m!互素的数+m!依旧与m!互素，每m!个看作一组，则1..m!中有phi(m!)*(n!/m!)的数与m!互素。即求：
n!(1-1/p1)(1-1/p2)(1-1/p3)… mod R
=n!(1-p1)(1-p2)(1-p3)…/(p1*p2*p3…) mod R
其中p1…为m!的质因子即m以内所有的素数。
除法直接乘上一个逆元，用拓展欧几里得算法求一下。
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; typedef long long ll;
const int N = 1e7+; int fac[N],su[N],ans[N],tot;
int n,m,R,T,vis[N]; int gcd(int a,int b,int& d,int& x,int& y)
{
if(!b) { d=a; x=; y=; }
else { gcd(b,a%b,d,y,x); y-=x*(a/b); }
}
int inv(int a,int n)
{
int d,x,y;
gcd(a,n,d,x,y);
return d==? (x+n)%n:-;
} void get_pre()
{
fac[]=;
for(int i=;i<N;i++) fac[i]=(ll)fac[i-]*i%R;
for(int i=;i<N;i++) { //快速线性筛法求素数
if(!vis[i]) su[++tot]=i;
for(int j=;su[j]*i<N&&j<=tot;j++) {
vis[i*su[j]]=;
if(i%su[j]==) break;
}
}
ans[]=;
for(int i=;i<N;i++) {
ans[i]=ans[i-];
if(!vis[i]) ans[i]=(ll)ans[i]*(i-)%R*inv(i,R)%R;
}
} int main()
{
scanf("%d%d",&T,&R);
get_pre();
while(T--) {
scanf("%d%d",&n,&m);
printf("%lld\n",(ll)fac[n]*ans[m]%R);
}
return ;
}