由于n!是m!的倍数,而对于每个与m!互质且小于m!的数x,x+m!、x+2*m!……也与其互质,所以答案即为(n!/m!)*φ(m!)。
φ(m!)=m!*∏(1-1/pi)。其中的pi即为1~m中所有质数。那么这个前缀积就可以预处理了。
当n、m大于p的时候是可能有问题的,数据里没有就懒得讨论了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 10000010
int T,P,prime[N],exphi[N],cnt=;
int fac[N],inv[N],inv2[N];
bool flag[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj2186.in","r",stdin);
freopen("bzoj2186.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
T=read(),P=read();
fac[]=;for (int i=;i<min(P,N-);i++) fac[i]=1ll*fac[i-]*i%P;
inv[]=;for (int i=;i<min(P,N-);i++) inv[i]=(P-1ll*(P/i)*inv[P%i]%P)%P;
inv2[]=;for (int i=;i<min(P,N-);i++) inv2[i]=1ll*inv2[i-]*inv[i]%P;
flag[]=;
for (int i=;i<min(P,N-);i++)
{
if (!flag[i]) prime[++cnt]=i;
for (int j=;j<=cnt&&prime[j]*i<=N-;j++)
{
flag[prime[j]*i]=;
if (i%prime[j]==) break;
}
}
exphi[]=;
for (int i=;i<min(P,N-);i++)
if (!flag[i]) exphi[i]=1ll*exphi[i-]*(P+-inv[i])%P;
else exphi[i]=exphi[i-];
for (int i=;i<min(P,N-);i++)
exphi[i]=1ll*exphi[i]*fac[i]%P;
while (T--)
{
int n=read(),m=read();
printf("%d\n",1ll*fac[n]*inv2[m]%P*exphi[m]%P);
}
return ;
}