题目大意：给定询问组数T和取模数P，每次询问给定两个整数n和m，求1~(n!)的数中与m!互质的数个个数模P (m<=n)

首先T<=1W，暴力肯定过不去，我们须要预处理一些东西

首先我们知道，若x与y互质，则x+y与y也互质，x+2y与y也互质。。。

换到这道题上来说，若一个数x与m!互质，那么x+(m!)也一定与m!互质，(x+m!*2)也一定与m!互质。。。

因为n!一定是m!的倍数，于是我们每存在到一个x<=m!与m!互质，我们就一定能找到(n!)/(m!)个与m!互质的数

而m!以内与m!互质的数的数量恰好是φ(m!)

于是我们要得到的数恰好就是φ(m!)*(n!)/(m!) %p

当中m!的全部质因数恰好就是m以内全部的质数 于是φ(m!)=(m!)*∏(pi-1)/pi (pi<=m)

于是最后我们的结果就是n!*∏(pi-1)/pi

质数预处理出来，n!预处理出来，pi的逆元预处理出来，∏(pi-1)/pi就能够预处理出来，都是线性的

至于pi的逆元 有一个比較快的线性求法(详见 http://blog.csdn.net/whyorwhnt/article/details/19169035 )

我的代码最后交上去超时了1.5秒AC。。。并且我还不是最慢的，wulala大神比我还要慢200+MS。。。

#include<bitset>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 10000001

using namespace std;

typedef long long ll;

bool not_prime[M+100];

ll prime[500500],ans[M+100],fac[M+100],rev[M+100];

int n,m,p,T,tot;

void Linear_Shaker()

{

	ll i,j;

	for(i=2;i<=M;i++)

	{

		if(!not_prime[i])

			prime[++tot]=i;

		for(j=1;j<=tot&&prime[j]*i<=M;j++)

		{

			not_prime[prime[j]*i]=1;

			if(i%prime[j]==0)

				break;

		}

	}

	fac[1]=1;

	for(i=2;i<=M;i++)

		fac[i]=fac[i-1]*i%p;

	rev[1]=1;

	for(i=2;i<=M&&i<p;i++)

		rev[i]=(p-p/i)*rev[p%i]%p;

	ans[1]=1;

	for(i=2;i<=M;i++)

	{

		if(!not_prime[i])

			ans[i]=ans[i-1]*(i-1)%p*rev[i%p]%p;

		else

			ans[i]=ans[i-1];

	}

}

int main()

{

	scanf("%d%d",&T,&p);

	Linear_Shaker();

	for(int i=1;i<=T;++i)

	{

		scanf("%d%d",&n,&m);

		printf("%d\n",fac[n]*ans[m]%p);

	}

}