bzoj 2186 [Sdoi2008]沙拉公主的困惑（欧拉函数，逆元）

【题目链接】

http://www.lydsy.com/JudgeOnline/problem.php?id=2186

【题意】

若干个询问，求1..n!中与m!互质的个数。

【思路】

首先有gcd(a,b)=gcd(a+b,b)，则一个与m!互素的数+m!依旧与m!互素，每m!个看作一组，则1..m!中有phi(m!)*(n!/m!)的数与m!互素。即求：

n!(1-1/p1)(1-1/p2)(1-1/p3)… mod R

=n!(1-p1)(1-p2)(1-p3)…/(p1*p2*p3…) mod R

其中p1…为m!的质因子即m以内所有的素数。

除法直接乘上一个逆元，用拓展欧几里得算法求一下。

【代码】

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 const int N = 1e7+3;
 8 
 9 int fac[N],su[N],ans[N],tot;
10 int n,m,R,T,vis[N];
11 
12 int gcd(int a,int b,int& d,int& x,int& y)
13 {
14     if(!b) { d=a; x=1; y=0; }
15     else { gcd(b,a%b,d,y,x); y-=x*(a/b); }
16 }
17 int inv(int a,int n)
18 {
19     int d,x,y;
20     gcd(a,n,d,x,y);
21     return d==1? (x+n)%n:-1;
22 }
23 
24 void get_pre()
25 {
26     fac[1]=1;
27     for(int i=2;i<N;i++) fac[i]=(ll)fac[i-1]*i%R;
28     for(int i=2;i<N;i++) {                                            //快速线性筛法求素数 
29         if(!vis[i]) su[++tot]=i;
30         for(int j=1;su[j]*i<N&&j<=tot;j++) {
31             vis[i*su[j]]=1; 
32             if(i%su[j]==0) break;
33         }
34     }
35     ans[1]=1;
36     for(int i=2;i<N;i++) {
37         ans[i]=ans[i-1];
38         if(!vis[i]) ans[i]=(ll)ans[i]*(i-1)%R*inv(i,R)%R;
39     }
40 }
41 
42 int main()
43 {
44     scanf("%d%d",&T,&R);
45     get_pre();
46     while(T--) {
47         scanf("%d%d",&n,&m);
48         printf("%lld
",(ll)fac[n]*ans[m]%R);
49     }
50     return 0;
51 }