題目的意思大概是求1~N!中和M！互質的數的個數

因為對歐拉函數理解不夠深刻所以我是分析得到結果的：

當N<=M的時候顯然符合要求的數的個數為0；

當N>M的時候我們要求的是1~N!中不含1 ~M的素因子的的數的個數，結合歐拉函數的推導過程（容斥原理）假設N!在1 ~ M中含有k個素因子，設n=N!，那么符合要求的數的個數就是

$n?n/p1?n/p2?...?n/pk+n/p1p2+n/p1p3+...+n/p(k?1)pk?...=n(1?1/p1)(1?1/p2)...(1?1/pk)$
因為我們不能首先求出n的大小再算（如果可以求出n的大小的話那顯然直接計算就可以，但是我們必須要模R），在模R的情況下我們應該求出pi的逆元，所以整個過程就是線性篩得到1~M的素數因子以及他們的逆元，然后與N!相乘計算（按照上面的公式）

我的代碼：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<ctime>
#include<climits>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e7+5;
int prime[MAXN];
bool check[MAXN];
int N[MAXN],r[MAXN],ans[MAXN];
int tot;
ll R,n,m;void ex_gcd(int a,int b,int& d,int &x,int &y)
{if(!b) {d=a; x=1; y=0;}else{ex_gcd(b,a%b,d,y,x); y-=(a/b)*x;}
}int getine(int a)
{int x,y,d;ex_gcd(a,R,d,x,y); x=(x%R+R)%R;return x;
}void creat_prime()
{tot=0; r[1]=1; N[1]=1;for(int i=2;i<MAXN;i++){N[i]=(ll)N[i-1]*i%R;if(!check[i]){prime[tot++]=i;r[i]=getine(i);}for(int j=0;j<tot && prime[j]*i<MAXN;j++){check[prime[j]*i]=true;if(i%prime[j]==0) break;}}
}void init()
{ans[1]=1;for(int i=2;i<MAXN;i++){ans[i]=ans[i-1];if(!check[i]) ans[i]=(ll)ans[i]*(i-1)%R*r[i]%R;}
}int main()
{int T;scanf("%d%d",&T,&R);creat_prime();init();while(T--){scanf("%d%d",&n,&m);printf("%d\n",(ll)N[n]*ans[m]%R);}return 0;
}

雖然可以得到正確的答案，但是經過了自己的推導分析，思維質量比較低。根本原因還是對歐拉函數的理解不夠深刻。

讓我們再來看看歐拉函數的意義：求出1~n中和n互質的數的個數，那么1 ~kn中與n互質的數的個數有多少呢？答案是k*phi[n]（結合上面推導也可以發現這個）。為什么是這樣呢？

互質即意味著$gcd(x,n)=1$，由最大公約數的性質我們得到$gcd(x+kn,n)=1$即這個數在每次kn+1~(k+1)n中都會出現一次，所以答案是k*phi[n]

回到這個問題：題目要求1~N!中和M!互質的數的個數，那么答案應該是N!/M!*phi[M!]，再結合歐拉函數值的求法可以得到上面的過程。

學習了一下遞推法求逆元.(遞推法求逆元如果不是都要用時間還是慢一點)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<ctime>
#include<climits>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e7+5;
int prime[MAXN];
bool check[MAXN];
int N[MAXN],r[MAXN],ans[MAXN];
int tot;
ll R,n,m;int read()
{int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x;
}void ex_gcd(int a,int b,int& d,int &x,int &y)
{if(!b) {d=a; x=1; y=0;}else{ex_gcd(b,a%b,d,y,x); y-=(a/b)*x;}
}int getine(int a)
{int x,y,d;ex_gcd(a,R,d,x,y); x=(x%R+R)%R;return x;
}void creat_prime()
{tot=0; r[1]=1; N[1]=1;for(int i=2;i<MAXN;i++){N[i]=(ll)N[i-1]*i%R;if(!check[i]){prime[tot++]=i;//r[i]=getine(i);}for(int j=0;j<tot && prime[j]*i<MAXN;j++){check[prime[j]*i]=true;if(i%prime[j]==0) break;}}for(int i=2;i<MAXN&&i<R;i++)r[i]=R-(ll)R/i*r[R%i]%R;
}void init()
{ans[1]=1;for(int i=2;i<MAXN;i++){ans[i]=ans[i-1];if(!check[i]) ans[i]=(ll)ans[i]*(i-1)%R*r[i]%R;}
}int main()
{int T;T=read(); R=read();creat_prime();init();while(T--){n=read(); m=read();printf("%d\n",(ll)N[n]*ans[m]%R);}return 0;
}