BZOJ-2186 沙拉公主的困惑 线性筛（筛筛筛）+线性推逆元

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

Time Limit: 10 Sec Memory Limit: 259 MB

Submit: 2417 Solved: 803

[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

HINT

Source

显然答案为：



于是线性筛出质数，线性推出阶乘，再线性处理处 累乘，最后线性推出逆元；

模p意义下逆元线性推法：(inv[1]=1;) inv[i]=(p-p/i)*inv[p%i]%p;

一开始我好像在BZOJ上被卡常了？

code：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,t,p;
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;
}
#define maxn 10000010
int prime[1000001];
bool flag[maxn]={0};
long long inv[maxn];
long long jc[maxn];
long long ans[maxn];

int quick_pow(long long a,int b,int p)
{
    int ans=1;
    for(int i=b;i;i>>=1,a=(a*a)%p)
        if(i&1)ans=(ans*a)%p;
    return ans;
}

void get()
{
    memset(flag,0,sizeof(flag));
    flag[1]=1; inv[1]=1;jc[1]=1;
    int cnt=0;
    for (int i=2; i<=maxn; i++)
        {
            jc[i]=jc[i-1]*i%p;
            if (i<p) inv[i]=(long long)(p-p/i)*inv[p%i]%p;
            if (!flag[i])
                prime[++cnt]=i;
            for (int j=1; j<=cnt && i*prime[j]<=maxn; j++)
                {
                    flag[i*prime[j]]=1;
                    if (i%prime[j]==0) break;
                }
        }
    ans[1]=1;
    for (int i=2; i<=maxn; i++)
        if (!flag[i])
            ans[i]=ans[i-1]*(i-1)%p*inv[i%p]%p;
        else
            ans[i]=ans[i-1];
}

int main()
{
    t=read(),p=read();
    get();
    while (t--)
        {
            n=read(),m=read();
            printf("%d\n",ans[m]*jc[n]%p);
        }
    return 0;
}