一:前置知识点
a:欧几里得算法:
1:欧几里得算法欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。
2:欧几里得算法证明:
两个引理:
若d是a和b的公约数,那么d也是b和c的公约数(c=a%b)若d是b和c的公约数(c=a%b),那么d也是a和b的公约数
按照辗转相除法如此循环下去,每次的余数r小于除数n ,那么相当于每次的被除数(变为上次的的除数)变小了,除数也变小了,而公因数的集合一直都没有变,也就是被除数和除数越来越小,而二者所包含的公共公因数又不变这样循环下去,最后除数就会变为最大公因数
3:代码模板
int gcd(int a ,int b){return b ? gcd(b,a%b ) : a ;}
b: 倍祖定理
任意两个整数a,b,最大公约数为d=gcd(a,b),那么对于任意的整数x,y,ax+by=m,构成的m一定是d的整数倍(即m%d=0)
二:扩展欧几里得初识:
扩展欧几里得算法(英语:Extended Euclidean algorithm)是欧几里得算法(又叫辗转相除法)的扩展。已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足贝祖等式
ax + by = gcd(a,b)
如果a是负数,可以把问题转化成|a|(-x)+by = gcd(|a|,b),然后令x'=(-x)。
通常谈到最大公约数时,我们都会提到一个非常基本的事实:给予二个整数a、b,必存在整数x、y使得ax + by = gcd(a,b)。
有两个数a,b,对它们进行辗转相除法,可得它们的最大公约数——这是众所周知的。然后,收集辗转相除法中产生的式子,倒回去,可以得到ax+by=gcd(a,b)的整数解。
扩展欧几里得算法可以用来计算模反元素(也叫模逆元),而模反元素在RSA加密算法中有举足轻重的地位。
三:扩展欧几里得的应用:
1:求二元一次线性方程的整数解
扩展欧几里得算法的描述是:一定存在整数 x, y 满足等式 a * x + b * y = gcd(a,b)
所以扩展欧几里得算法可以计算出最大公因数gcd(a,b),又可以为计算出x,y的一组特解,如何求解呢
带入等式:gcd(b,a%b) = bx1 + (a%b)*y1gcd(b,a%b) =b*x1+(a-(a/b)*b)*y1gcd(b,a%b) = a*y1 + b*(x1-(a/b)*y1)当b不等于0时,gcd(a,b) = gcd(b,a%b);所以 x= y1 ; y = x1 - (a/b) *y1 ;
根据这个过程,我们可以递归求解,那退出条件是什么呢,我们可以看到当b==0 是,求出公约数
,当b==0 是,a*x = gcd(a,0) = a ,此时,x==1 ,y等于0可以计算出一组特解
代码模板:
//求x,y 使得ax + by = gcd(a,b) ;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);int temp = y ;y= x-(a/b)*y ; x= temp ; return d ; }
2: 乘法逆元
这里先说一下乘法逆元,我们都知道,‘取模%’ 具有加、减、乘法的分配率即:
1). (a+b) % c = ((a%c) + (b%c))%c
2). (a-b) % c = ((a%c) - (b%c))%c
3). (a×b) % c = ((a%c)× (b%c))%c
这样的好处就是,如果a+b+…+n计算出来的值太大的话,可以通过分配率来计算出每一步的值在求余。
除法没有分配率,但是有乘法逆元。就是将除法转化为乘法。
逆元:设c是b的逆元,则有ax ≡ 1(mod p);
(a/b)mod p = (a/b) * 1(mod p) = (a/b)bx (mod p) = ax(mod p)
定理:a存在模p的乘法逆元的充要条件是gcd(a,p) = 1;(定理的证明在这里就不叙述了)
对于ax + by = 1,可以看出x是a模b的乘法逆元,y是b模a的乘法逆元。
四:题目练习
同余方程(传送门)
题目描述:求关于xx的同余方程ax≡1(modb)的最小正整数解。
输出格式
一个正整数x_0x0,即最小正整数解。输入数据保证一定有解。
输入输出样例
输入 #1复制
3 10
输出 #1
7
分析
板子题,唯一需要做的就是转化一下将ax ≡ 1( mod b ) 变为 ax - by = 1 的形式,最后由于输出最小的正整数,我们调整一下即可
#include <bits/stdc++.h>using namespace std ;int a,b ,x,y,k; void exgcd (int a, int b ){if(!b){x=1 ; y = 0 ;return ; }exgcd(b,a%b);int temp = y ;y= x-(a/b)*y ; x= temp ; return ; } int main(){cin >> a>>b ; exgcd(a,b) ; cout << (x+b)%b << endl ; }
五:注意:
如果需要求该方程的最小非负整数解,该如何调整?
容易发现 a x + b y = g c d ( a , b ) ,等价于a ∗ ( x − k ∗ b ) + b ∗ ( y + k ∗ a ) = g c d ( a , b )
所以对于x的调整为x=(x%b+b)%b
对于y的调整为y=(y%a+a)%a