[Sdoi2008]沙拉公主的困惑

2186: [Sdoi2008]沙拉公主的困惑

Time Limit: 10 Sec Memory Limit: 259 MB
[Submit][Status][Discuss]

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

1 11
4 2

Sample Output

1

数据范围：
对于100%的数据，1 < = N , M < = 10000000

ans=phi（m！）*n！/m！

原理见 http://www.cnblogs.com/TheRoadToTheGold/p/7398072.html

如果预处理出所有的 phi（m！） * m！的逆元，TLE 60

phi（m！）= m！* π（1-1/pi）

恰好可以把m！约去

所以 ans= n！* π （1-1/pi）

递推求 π （1-1/pi）

#include<cstdio>

#define N 10000001

using namespace std;

int mod;

int f[N],fac[N],inv[N];

int p[N],cnt;
bool vis[N];

void pre_prime()
{
    vis[1]=true; inv[1]=1;
    for(int i=2;i<N;i++)
    {
        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
        if(!vis[i]) p[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            if(p[j]*i>=N) break;
            vis[p[j]*i]=true;
            if(i%p[j]==0) break;
        }
    }
}

void pre_fac()
{
    fac[1]=f[1]=1;
    for(int i=2;i<N;i++) 
    {
        fac[i]=1ll*fac[i-1]*i%mod;
        f[i]=f[i-1];
        if(!vis[i]) f[i]=1ll*f[i]*(i-1)%mod*inv[i]%mod;
    }
}

int main()
{
    int t;
    scanf("%d%d",&t,&mod);
    pre_prime();
    pre_fac();
    int n,m;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        printf("%d
",1ll*fac[n]*f[m]%mod);
    }
}