一、欧拉函数
1、定义：对于正整数n，欧拉函数φ(x)是求小于n中与n互质的数字的数目。
2、公式：
φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) 其中p(1),p(2)…p(n)为x
的所有质因数;x是正整数; φ(1)=1(唯一和1互质的数，且小于等于1)。注意：每种质因数只有一个。
3、代码实现：
//求小于等于n且与n互质的数字的个数 int Euler(int n) {int i,ans=n;for(i=2;i<=sqrt(n);i++){if(n%i==0){ans=ans/i*(i-1); //先除，防止数据溢出 while(n%i==0) n/=i;}}if(n>1){ans=ans/n*(n-1);}return ans; } //筛选1-n之间每个数的质因数的个数 void Init(int n) {memset(euler,0,sizeof(euler));euler[1]=1;for(int i=2;i<n;i++)if(!euler[i]){for(int j=i;j<n;j+=i){if(!euler[j]) euler[j]=j;euler[j]=euler[j]/i*(i-1);}} }
参考文章：传送门
二、费马小定理
1、内容：
假如p是质数，a与p为互质数，则a的p-1次方除以p的余数恒等于1 。
参考文章：传送门