BZOJ2186 欧拉函数

欧拉函数：一般记作φ(n)，表示1-n中与n互质的数的数量。

欧拉函数是积性函数，即φ(m*n)=φ(m)*φ(n)　　　　//这条定理基友面试时还遇到了= =

欧拉函数的值φ(n)=n*(1-p[1])*(1-p[2])*...*(1-p[n])　　//p[i]是小于等于n的所有素数

若n是m的倍数，则小于等于n且与m互质的数的个数为(n/m)*φ(m)　　　　//证明不难理解：设k小于等于m且与m互质，则k+m、k+2m......也与m互质

若n是质数p的k次幂，则φ(n)=(p-1)*(p^(k-1))

//关于欧拉函数wikipedia上讲的很详细，此处不赘述了

若a mod b=0，可记作b|a

那么原题的答案就是(n!/m!)*φ(m!)

isprime(n)：计算1-n的质数

calc_fac(n)：计算1-n每个数的阶乘

calc_inv(n)：计算1-n每个数的逆元

calc_eul(n)：计算(1-1/p1)*(1-1/p2)*...*(1-1/pn)

　　　　　　　设x[i]=inv(p[i])，那么

　　　　　　　(1-1/p[i]) mod m

　　　　　　= ( (1 mod m) - ( (1/p[i]) mod m ) ) mod m

　　　　　　= (m+1-( (1/p) mod m ) mod m

　　　　　　 而根据逆元的性质，有(1/p) mod m=x mod m

Reference：http://blog.csdn.net/acdreamers/article/details/8220787

　　　　　　http://www.cnblogs.com/autsky-jadek/p/4054971.html

附SDOI官方题解：

 1 该题即求1至n!中与m!互质的数对某质数R取模后的值 。
 2 对于每一对数N，M，设p1,p2,……pn为不大于M的质数，题目即求在1至N！中，不包含因子p1,p2,……pn的数的个数。
 3 在1至N！中，p1的倍数有N!/p1个，p2的倍数有n!/p2个……p1p2的倍数有n!/p1p1个……p1p2p3..pkm的倍数有n!/p1p2p3..pkm个。
 4 由容斥定理得答案为：
 5 n!-n!/p1-n!/p2-n!/p2…-n!/pkm+n!/p1p2+n!/p1p3……+(-1)^km*n!/p1p2p3…pkm= n!*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…*(1-1/pkm)
 6 记m!* (1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…*(1-1/pkm)为fi[m]。答案为n!/m!*fi[m]。
 7 根据fi的计算式，可得fi的递推式为
 8 Fi[i]=fi[i-1]*i（当i为合数）
 9 Fi[i]=fi[i-1]*(i-1)（当i为质数）
10 
11 预处理得所有fi与i!，通过扩展GCD计算除法，可在O(logR)时间内计算得每一个解。

View Code

各种卡时限，cin、cout是用不了的，关了同步都不行>_<

 1 #include "cstring"
 2 #include "math.h"
 3 #include "stdio.h"
 4 using namespace std;
 5 #define MMX 10000002
 6 #define LL long long
 7 LL M,N,T,MOD;
 8 LL fa[MMX],inv[MMX],ans2[MMX];
 9 bool pr[MMX];
10 
11 void isprime(LL n)     //pr[i]=1 : i is a prime
12 {
13     memset(pr,true,sizeof(pr));
14     LL m=sqrt(n+0.5);
15     pr[1]=false;
16     for (LL i=2;i<=m;i++)
17         if (pr[i])
18         {
19             for (LL j=i*i;j<=n;j+=i)
20                 pr[j]=false;
21         }
22 }
23 
24 void calc_fac(LL n)      //fa[i]=i!
25 {
26     fa[0]=1;
27     for (LL i=1;i<=n;i++)
28         fa[i]=fa[i-1]*i%MOD;
29 }
30 
31 void calc_inv(LL n)      //inv[i]
32 {
33     inv[1] = 1;
34     for(int i=2;i<n;i++)        //inv[i]:逆元
35     {
36         if(i >= MOD) break;
37         inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
38     }
39 }
40 
41 void calc_eul(LL n)
42 {
43     ans2[1] = 1;            //ans2[i]=(1-1/p1)*(1-1/p2)*...*(1-1/pi)
44     for(LL i=2; i<n;i++)        //又(1-1/pi)=((pi-1)/pi)
45     {
46         if(pr[i])
47         {
48             ans2[i] = ans2[i-1] * (i - 1) % MOD;
49             ans2[i] = ans2[i] * inv[i % MOD] % MOD;
50         }
51         else
52         {
53             ans2[i] = ans2[i-1];
54         }
55     }
56 }
57 
58 int main()
59 {
60     scanf("%d%d",&T,&MOD);
61     isprime(MMX);
62     calc_inv(MMX);
63     calc_fac(MMX);
64     calc_eul(MMX);
65     while (T--)
66     {
67         scanf("%d%d",&N,&M);
68         //ans=(N!/M!)*f(M!)
69         //   =N!*[(1-1/p1)*...*(1-1/pi)]
70         LL ans=fa[N]*ans2[M]%MOD;
71         printf("%lld
",ans);
72     }
73 
74     return 0;
75 }

最后过得好险= =

771794

i386DX

2186

Accepted

244956 kb

11312 ms

C++/Edit

1653 B

2014-11-04 23:34:15