10.27T5 欧拉函数

2819 -- 【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

Hint

【数据范围】
　　对于20%的数据， 1<=N,M<=10,T<=10
　　对于40%的数据， 1<=N,M<=10000
　　对于80%的数据， 1<=N,M<=1000000
　　对于100%的数据，1<=N,M<=10000000

明显n=m时答案是phi(m!)，当我们n继续变大的时候可以证明若x与m!互质，则x+km!同样与m!互质

所以答案就是Phi(m!)*n!/m!

我们递推m!的欧拉函数的时候我们可以有以下引理

我们就可以O(n)预处理了

注意，我们在预处理阶乘的逆元的时候在这个情况下不可以使用公式inv[i]=inv[i+1]*(i+1)%mod，因为我们平时用的时候保证模数是足够大的，所以不会出现到后面一堆零

比如样例，当我们预处理1e7的逆元的时候如果用原来的方法，由于11之后的阶乘取模都是0，所以快速幂求逆元全是0，明显1的逆元不是0

所以我们的解决方法是询问到的时候直接计算fac[m]^(mod-2)%mod就可以解决这个问题了

code：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 long long T,R,cnt;
 5 long long Min[10000006],phi[10000006],inv[10000006],zs[10000006],fac[10000006];
 6 long long ksm(long long a,long long b) {
 7     long long ans=1;
 8     for(; b; b>>=1) {
 9         if(b&1) {
10             ans*=a;
11             ans%=R;
12         }
13         a*=a;
14         a%=R;
15     }
16     return ans;
17 }
18 void pre1() {
19     for(long long i=2; i<=10000000; i++) {
20         if(Min[i]==0) {
21             Min[i]=i;
22             zs[++cnt]=i;
23         }
24         for(long long j=1; j<=cnt; j++) {
25             if(zs[j]>Min[i]||zs[j]*i>10000000)break;
26             Min[zs[j]*i]=zs[j];
27         }
28     }
29 }
30 void pre2() {
31     phi[0]=phi[1]=1;
32     for(long long i=2; i<=10000000; i++) {
33         if(Min[i]==i) {
34         //    cout<<i<<" ";
35             phi[i]=(phi[i-1]*(i-1))%R;
36         } else {
37             phi[i]=(phi[i-1]*i)%R;
38         }
39     }
40 }
41 void pre3() {
42     fac[0]=1;
43     for(long long i=1; i<=10000000; i++) {
44         fac[i]=(fac[i-1]*i)%R;
45 //        cout<<fac[i]<<" ";
46 //        system("pause");
47     }
48     inv[10000000]=ksm(fac[10000000],R-2);
49 }
50 int main() {
51     cin>>T>>R;
52     pre1();
53     pre2();
54     pre3();
55     while(T--) {
56         long long n,m;
57         cin>>n>>m;
58     //    cout<<phi[m]<<" "<<fac[n]<<" "<<inv[m]<<'
';
59         cout<<((phi[m]*fac[n])%R*ksm(fac[m],R-2))%R<<'
';
60     }
61     return 0;
62 }

over