bzoj2186【SDOI2008】沙拉公主的困惑

bzoj2186【SDOI2008】沙拉公主的困惑

Description

　　大富翁國因為通貨膨脹，以及假鈔泛濫，政府決定推出一項新的政策：現有鈔票編號范圍為1到N的階乘，但是，政府只發行編號與M!互質的鈔票。房地產第一大戶沙拉公主決定預測一下大富翁國現在所有真鈔票的數量。現在，請你幫助沙拉公主解決這個問題，由於可能張數非常大，你只需計算出對R取模後的答案即可。R是一個質數。

Input

第一行為兩個整數T，R。R<=10^9+10，T<=10000，表示該組中測試數據數目，R為模後面T行，每行一對整數N，M，見題目描述 m<=n

Output

共T行，對於每一對N，M，輸出1至N！中與M！素質的數的數量對R取模後的值

Sample Input

Sample Output

HINT

Source

數論

歐拉函數+線性篩法+ 乘法逆元

數論題的做法簡直不能再6，感覺自己智商嚴重不夠用…

首先答案為phi(m!)*n!/m!%p。因為所有小於m!且與m!互質的數加上m!的整數倍都與m!互質，而其他數都不與m!互質。(正確性顯然)

那麼這個式子怎麼求呢？？？

我們可以分成兩部分來求，phi(m!)/mi和n!。

n!%p是很容易預處理的，這裡的主要問題是如何求phi(m!)/m!。

令f(m)=phi(m!)/m!，根據phi(x)=x*(p1-1)/p1*(p2-1)/p2*…

可得f(m)=(p1-1)/p1*(p2-1)/p2*…其中pi為不大於m的質數

所以對於f(i)，如果i是質數f(i)=f(i-1)*(i-1)/m，否則f(i)=f(i-1)。

根據以上關系式可以預處理f(1)-f(10^7)。

每次詢問只需要輸出f(m)*n!%p即可。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 10000005
using namespace std;
int n,m,p,t;
ll fac[maxn],ans[maxn];
bool f[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void exgcd(int a,int b,int &x,int &y)
{
	if (!b){x=1;y=0;return;}
	exgcd(b,a%b,x,y);
	int t=x;x=y;y=t-a/b*x;
}
inline int getinv(int a)
{
	int x=0,y=0;
	exgcd(a,p,x,y);
	return (x%p+p)%p;
}
int main()
{
	t=read();p=read();
	int x=10000000;
	fac[1]=1;
	F(i,2,x) fac[i]=fac[i-1]*i%p;
	ans[1]=1;
	F(i,2,x)
	{
		if (!f[i])
		{
			ans[i]=ans[i-1]*(i-1)%p*getinv(i)%p;
			F(j,2,x/i) f[i*j]=true;
		}
		else ans[i]=ans[i-1];
	}
	while (t--)
	{
		n=read();m=read();
		printf("%lld\n",ans[m]*fac[n]%p);
	}
}