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

1 11

4 2

Sample Output

1

数据范围：

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

分析

首先面向数据范围编程，可知复杂度是 $O\left(m\right)$O(m) 。

注意到 $m!\mid n!$m!∣n!，且 $gcd(a,b)=gcd(a+kb,b)$gcd(a,b)=gcd(a+kb,b)，可以发现 $ans=\phi (m!)\ast n!/m!$ans=φ(m!)∗n!/m!，
由 $\phi (m!)=m!(1-\frac{1}{p_1})...(1-\frac{1}{p_k})$φ(m!)=m!(1−p1​1​)...(1−pk​1​)，可知
$ans=n!\ast (1-\frac{1}{p_1}).....(1-\frac{1}{p_k})$ans=n!∗(1−p1​1​).....(1−pk​1​)
令 $f\left(n\right)=n!$f(n)=n!， $g\left(m\right)=(1-\frac{1}{p_1}).....(1-\frac{1}{p_k})$g(m)=(1−p1​1​).....(1−pk​1​)，分别在线性时间内预处理出来即可。

代码如下

#include <bits/stdc++.h>
#define N 10000005
#define LL long long
using namespace std;
int x[N], p[N], inv[N], fac[N], w[N], cnt, P;
LL z = 1, t;
void exgcd(int a, int b, int &x, int &y){
    if(!b) x = 1, y = 0;
    else{
        exgcd(b, a % b, y, x);
        y -= a / b * x;
    }
} 
int main(){
    int i, j, n, m, T, las, a, b;
    scanf("%d%d", &T, &P);
    for(i = 2; i <= 10000000; i++){
        if(!x[i]) x[i] = p[++cnt] = i;
        for(j = 1; j <= cnt; j++){
            t = z * p[j] * i;
            if(t > 10000000) break;
            x[t] = p[j];
            if(i % p[j] == 0) break;
        }
    }
    for(fac[0] = i = 1; i <= 10000000; i++) fac[i] = z * fac[i-1] * i % P;
    w[1] = inv[1] = 1;
    //for(i = 2; i <= 10000000; i++) inv[i] = z * (P - P / i) * inv[P % i] % P;
    for(i = 1; i <= cnt; i++){
        exgcd(p[i], P, a, b);
        a = (a % P + P) % P;
        inv[p[i]] = a;
    }
    for(i = 2; i <= 10000000; i++){
        w[i] = w[i-1];
        if(x[i] == i) w[i] = z * w[i-1] * (i - 1) % P * inv[i] % P;
    }
    while(T--){
        scanf("%d%d", &n, &m);
        printf("%d\n", z * fac[n] * w[m] % P);
    }
    return 0;
}