本文主要是介绍第四章 数学知识 （二）（欧拉函数、快速幂、扩展欧几里得、中国剩余定理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、欧拉函数（1~n中有多少个数和n互质）
(一) 1~n 中和n互质的数
1、互质数：公约数为1的两个整数。
2、当n为6的时候：
3、容斥原理公式
4、定义法求某一个数的欧拉函数
#include<bits/stdc++.h>
//873 欧拉函数用公式定义法求某个数的欧拉函数
using namespace std;
int n;
int main()
{cin>>n;while(n--){int a;cin>>a;int res=a;for(int i=2;i<=a/i;i++)//质数分解{if(a%i==0){//根据公式(1-1/i)变形res=res/i*(i-1);while(a%i==0)a/=i;}}if(a>1)res=res/a*(a-1);cout<<a<<endl;}
}
5、筛法求欧拉函数，求1-n中某一个数的欧拉函数
求1~n中欧拉函数的和。质数的欧拉函数为n-1。
利用线性筛法，每次遍历到的st为false的数（质数）可以直接算出来欧拉函数；在遍 历之前的所有素数筛掉合数的时候，
#include<bits/stdc++.h>
//874 筛法求欧拉函数 求1-n的欧拉函数的和
using namespace std;
typedef long long LL;
const int N=1e6+10;
int prime[N],phi[N],idx,st[N];//分别记录素数、欧拉函数、是否被筛选掉
LL get_eulers(int n)
{//从2开始算的phi[1]=1;//这里i不是数组的下标是真正遍历到的数for(int i=2;i<=n;i++){//素数if(!st[i])phi[i]=i-1,prime[idx++]=i;for(int j=0;prime[j]<=n/i;j++){st[i*prime[j]]=true;if(i%prime[j]==0){//pj是i的最小质因数，所以欧拉函数的结果只乘pj即可phi[i*prime[j]]=prime[j]*phi[i];break;}//如果不是需要乘以pj*(1-1/pj)phi[i*prime[j]]=phi[i]*(prime[j]-1);}}LL res=0;for(int i=0;i<=n;i++)res+=phi[i];return res;
}
int main()
{int n;cin>>n;cout<<get_eulers(n);return 0;
}
(二) 欧拉定理
当n和p互质的时候（费马定理）
（可证）p mod n（p除n的余数）与n互质。若此结论成立，则也有 pi ≡ xj(mod n)。
二、快速幂（O(log k)快速求出a^k mod p）
（一）快速幂基础算法实现
1、求法：将k分解为多个 （2^x1+……）相加的结果。只需要计算以a为底 2^xi次方为指数的值的乘积。
计算单个的时候，每一个都是上一个的平方。
4^5举例：要知道存在一个对应的等价关系:将k分解为二进制相加的形式，目的就是为了转换为以a为底的数的乘法，累计得到结果。每次循环都更新a。
快速幂计算
#include<bits/stdc++.h>
//875 快速幂
using namespace std;
typedef long long LL;
int qmi(int a,int k,int p)
{int res=1;while(k){//注意判断某个数的二进制最后一位的值的方法if(k&1)res=(LL)res*a%p;k>>=1;a=(LL)a*a%p;}return res;
}
int main()
{int n;cin>>n;while(n--){int a,k,p;cin>>a>>k>>p;cout<<qmi(a,k,p)<<endl;}
}(二)、快速幂求逆元（求逆元可以转化为求快速幂）
如果b可以整除a，整除后的结果可以找到一个x使得a*x在mod m的情况下相同。x为b的模m逆元。
也就是可以把除以b转换为乘以b的逆元的情况。
转化为求下列式子的x的值。
根据费马小定理（若b和p互质）
无解的情况：b是p的倍数的时候无解
#include<bits/stdc++.h>
//876 快速幂求逆元
using namespace std;
typedef long long LL;
int qmi(int a,int k,int p)
{int res=1;while(k){//注意判断某个数的二进制最后一位的值的方法if(k&1)res=(LL)res*a%p;k>>=1;a=(LL)a*a%p;}return res;
}
int main()
{int n;cin>>n;while(n--){int b,p;cin>>b>>p;int res=qmi(b,p-2,p);//注意判断是否有结果的条件if(b%p)cout<<res<<endl;else puts("impossible");}
}三、扩展欧几里得算法
(一)裴蜀定理
（a,b）为ab的最大公约数。
由于ab凑出来的数一定是最大公约数的倍数。一定可以凑出这个最大公约数
877求xy（x,y）是不唯一的。
扩展欧几里得求解xy。还是递归的思想，如果b==0，最大公因数为a，x=1,y=0；结束即可；
递归就要明白两层之间的关系，与欧几里得算法类似，ax+by=gcd 的下一层是bx1+a%b y1=gcd;我们先得到的x1和y1，然后用找x1 y1和x y的关系，化简上面的式子 得到 ay1+b(x1-(a/b)*y1)=gcd
得到两层之间的关系。
#include<bits/stdc++.h>
//877 扩展欧几里得算法求xy
using namespace std;
typedef long long LL;
int exgcd(int a,int b,int &x,int &y)
{if(!b)//递归结束标志{x=1,y=0;return a;}int d=exgcd(b,a%b,x,y);//交换的意思是上一层的x1y1导到了这一层//会变成yx，此时x已经更新到位，并进一步更新y。int t=x;x=y;y=t;y-=(a/b)*x;
}
int main()
{int n,x,y;cin>>n;while(n--){int a,b;cin>>a>>b;exgcd(a,b,x,y);cout<<x<<" "<<y;}
}
(二)扩欧应用：求解线性同余方程
知道 a、b 、m求解x。
只要b是a和m的最大公约数的倍数就一定有解。
先按照结果为最大公约数算，如果b不是最大公约数的倍数，就无解，
#include<bits/stdc++.h>
//878 线性同余方程
using namespace std;
typedef long long LL;
int exgcd(int a,int b,int &x,int &y)
{if(!b)//递归结束标志{x=1,y=0;return a;}int d=exgcd(b,a%b,x,y);//交换的意思是上一层的x1y1导到了这一层//会变成yx，此时x已经更新到位，并进一步更新y。int t=x;x=y;y=t;y-=(a/b)*x;return d;
}
int main()
{int n,x,y;cin>>n;while(n--){int a,b,m;cin>>a>>b>>m;int x,y;int ans=exgcd(a,m,x,y);if(b%ans)puts("impossible");//目前式子求的是相加结果为最大公约数的结果//x需要再乘以（b/ans）mod melse cout<<x*(b/ans)%m<<endl;}
}四、中国剩余定理
m两两互斥，要求大括号里面成立，Mi^-1表示Mi以mi为模的逆。Mi是除了mi之外的所有m的乘积。最后得到的x的式子是满足所有的前面大括号的条件的。
这篇关于第四章 数学知识 （二）（欧拉函数、快速幂、扩展欧几里得、中国剩余定理）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
