Chapter 8. 数学基础 数论（二）
Sylvia's I. 欧拉函数.
内容：phi(x)等于不超过x且和x互质的整数个数.
公式：
，其中p1,p2,p3……pn为x的所有质因数，x是不为0的整数.
相关性质：
①欧拉函数是积性函数，但不是完全积性函数，仅在(m,n)=1，
.
②当n为奇数时， 
.
③若n为质数则，
.
④一个数n的所有质因子的和为(phi(n)*n)/2.
⑤除n=2之外，所有的phi(n)为偶数.
代码：
①用欧拉筛法顺便求欧拉函数
int cntprime = 0;int prime[MAXN];bool flag[MAXN];int phi[MAXN];int Euler(int n){ memset(phi,0,sizeof(phi)); phi[1]=1; memset(flag,false,sizeof(flag)); for (int i = 2; i <= n; i++) { if (!flag[i]) { prime[++cntprime] = i; phi[i]=i-1;//见性质③ } for (int j = 1; j <= cntprime && prime[j]*i <= n; j++) { flag[i*prime[j]] = true; if (i % prime[j] == 0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1);//性质①，phi[prime[j]]=prime[j]-1 } } return cntprime;} ②直接求解（摘自刘汝佳的蓝书）
void phi_table(int n,int *phi){ for(int i=2; i<=n; ++i) phi[i]=0; phi[1]=1; for(int i=2; i<=n; ++i) if(!phi[i]) for(int j=i; j<=n; j+=i) { if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); }}
Sylvia's II. Eratosthenes筛法.
原理：我们从2开始，每确定出一个质数，添加至IsPrime数组中，然后所有该质数的倍数标记为“不是质数”，如同一个筛子，把所有合数都筛下去.
代码：
#include#include #include #include using namespace std;#define MAXN 2333bool IsPrime[MAXN];//质数为true，合数为falseint n; int main(){ cin>>n; memset(IsPrime,true,sizeof(IsPrime)); //初始化，全部标记为是质数 IsPrime[1]=false;//1不是质数，为false for (int i=2;i<=sqrt(n)+1;i++)//如果是一个小于等于n的合数 //那么它的因子中一定有一个小于等于√n的质因子 if (IsPrime[i])//如果标记为是质数，那么就把它的倍数全部筛去 for (int j=i*i;j<=n;j+=i) IsPrime[j]=false; return 0;}
复杂度：O(nloglogn).
Sylvia's III.欧拉筛法.
原理：在Eratosthenes筛法中，有的数被筛了多次，如15被5和3筛了两次。此时我们采用欧拉筛法，保证每个合数只会被自己最小的质因子筛选，则我们可以得到一个复杂度O(n)的算法.
理论基础：
①任何一个合数都可以表示成一个质数和一个数的乘积.
②一个合数与一个质数的乘积可以表示成一个更大的合数与一个更小的质数的乘积.
③进一步说，任意一个合数，我们都可以拆成 最小质数*某个数字 的形式.
代码：
int cntprime = 0;//记录素数的个数int prime[MAXN];//记录素数bool flag[MAXN];//true为合数，false为素数int Euler(int n){ memset(flag,false,sizeof(flag));//初始化 for (int i = 2; i <= n; i++) { if (!flag[i]) prime[++cntprime] = i;//如果这是个素数，那么记录下来 for (int j = 1; j <= cntprime && prime[j]*i <= n; j++) { flag[i*prime[j]] = true;//注解① if (i % prime[j] == 0) break;//注解② } } return cntprime;}
注解①：合数标为true，prime[j]一定是合数i*prime[j]的最小素因子 ，为什么呢？注解②给出了解释，如果不是最小的质因子，那么早已经break了.
注解②：理解这一句是理解这个算法的关键. i有一个质因子是prime[j] ,那么i可以表示成i=prime[j]*x , x为一个整数，然后如果我们继续进行循环，那么下一次我们要标记的合数是flag[i*prime[j+1]] , 然而i=prime[j]*x，所以我们要标记的i*prime[j+1]这个合数相当于prime[j]*x*prime[j+1]]，它已经有一个最小的质因数是prime[j],所以这个数是我们已经标记过一次的，如果继续标记那么prime[j+1]并不是它的最小质因数，因此这一句是避免像Eratosthenes筛法重复标记的关键.
复杂度：O（n）.
Sylvia's Ⅳ.费马小定理.
内容：假如p为质数，且a，p互质，那么ap-1≡1（mod p).
应用：求逆元时，如果模数p是质数，求a的逆元只需计算ap-2%p.
Sylvia's Ⅴ.欧拉定理.
内容：若n,a为正整数，且n,a互质，则
.
应用：欧拉定理的一个重要意义就是计算a b mod m的时候，若b是一个很大的数时， 可以化成ab mod phi(m) mod m来计算.
Sylvia's Ⅴ.快速幂.
理论基础：
①ab mod c=(a mod c)b mod c
②由①推导出
ab mod c=((a2 mod c)b/2) mod c，当b为偶数.
ab mod c=((a2mod c)b/2*a) mod c ，当b为奇数.
代码：
int QuickPow(int a,int b,int p){ int ans=1; for (;b;a=(a*a)%p,b>>=1)//终止条件为b=0 if (b&1) ans=(ans*a)%p; return ans;}
复杂度：O（logn）
我与地坛
史铁生
当他熄灭着走下山去收尽苍凉残照之际，
正是他在另一面燃烧着爬上山巅布散烈烈朝辉之时。
Sylvia
二零一七年七月十九日