[bzoj2186] [洛谷P2155] [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###

1 11

4 2

Sample Output###

数据范围：

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

想法##

我们知道，对于一个数x，若y<x且y与x互质，那么y+x，y+2x，y+3x…都与x互质

那么对于这道题，N!内与M!互质的数的个数为

\[\begin{equation*}
\begin{aligned}
& \frac{N!}{M!} \varphi(M!) \\
=& \frac{N!}{M!} \times M! \times \frac{p1-1}{p1} \frac{p2-1}{p2}… （p1、p2…为M以内质数）\\
=& N! \times \frac{p1-1}{p1} \frac{p2-1}{p2}…
\end{aligned}
\end{equation*}
\]

这样就比较好了，预处理出 \(i!\) ，\(\frac{p1-1}{p1} \frac{p2-1}{p2}…\) 就行了

代码##

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long ll;

const int N = 10000005;

int n,m,T,R;

int inv[N],mi[N];

void init(){

    inv[1]=1; mi[1]=1;

    for(int i=2;i<N;i++){

        if(i<R) inv[i]=((ll)inv[R%i]*(R-R/i))%R;

        mi[i]=((ll)mi[i-1]*i)%R;

    }

}

int prime[N],sum[N],pnum,p[N];

void getp(){

    sum[1]=1;

    for(int i=2;i<N;i++) p[i]=1;

    for(int i=2;i<N;i++){

        if(p[i]) {

            prime[++pnum]=i;

            sum[i]=(((ll)sum[i-1]*(i-1))%R*(ll)inv[i%R])%R;

        }

        else sum[i]=sum[i-1];

        for(int j=1;j<=pnum && (ll)prime[j]*i<N;j++) {

            p[i*prime[j]]=0;

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

        }

    }

}

int main()

{

    int l,r,mid;

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

    init();

    getp();

    while(T--){

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

        printf("%lld\n",((ll)mi[n]*sum[m])%R);

    }

    return 0;

}

巴特西