欧几里得算法
欧几里得算法,既辗转相除法
求出最大公约数(公因子)
public static int gcd(int m,int n){
return n==0?m:gcd(n,m%n);
}
复杂度 粗略计算 在O(log max(a,b))
以内
变题
挑战程序设计P113 线段上的格点数
数学思维:
垂直距离与横向距离的最大公约数-1。其gcd就是可以划分的段数。
裴蜀(贝祖)等式
对任何整数a
、b
和它们的最大公约数d
,关于未知数x和y的线性丢番图方程(称为裴蜀(贝祖)等式)
ax+by=m(d)
有整数解
时候 当前仅当m
是d
(ab的最大公约数)的倍数
即gcd(a,c)=d ; ax+by=d
裴蜀(贝祖)等式 有解意味着必然有无穷多个整数解
,每组解x,y都被称作裴蜀(贝祖)数
可用扩展欧几里得算法(Extended Euclidean algorithm)求得 x,y。
例如
12x+42y=6
有解
因为12 42 是6的倍数 且6是其最大公约数
(4,-1),(11,-3).. 解都符合 >> 差值 △x=7 △y=2
而化简原式子 => 2x+7y=1 类似于跷跷板关系(一降一升)
所以a的增量(4->11)是7=(b/d) b的增量是2=(a/d)
增量: a=b/gcd b=a/gcd;
特别
的,方程 ax+by=1 有整数解当且仅当整数a和b互素
.(2,1)(2,3)有解;(2,4)无解
总结就是 只要求出贝祖等式的一个解就等得到无数个解
扩展欧几里得算法
gcd(a,b)
return b==0?a
观察:
欧几里德算法停止的状态是: a'= gcd , b' = 0 ,(a',b'是递归最后一层
时参数的值)
那么,这是否能给我们求解 x y 提供一种思路呢?
a'x + b'y = gcd 此时x=1,y为任意数
【此时的a,b不是原来的ab】
因为,这时候,只要 a = gcd 的系数是 1 ,那么只要 b 的系数是 0 或者其他值
(无所谓是多少,反正任何数乘以 0 都等于 0 但是a 的系数一定要是 1),
这时,我们就会有: a'1 + b'0 = gcd
反推
当然这是最终状态,但是我们是否可以从最终状态反推到最初的状态呢?
假设当前我们要处理的是求出 a 和 b的最大公约数
,并求出 x 和 y 使得
ax + by= gcd (1)
,--->要求的
而我们已经求出
了下一个状态:b 和 a%b 的最大公约数,并且求出了一组x1 和y1 使得:
bx1 + (a%b)y1 = gcd (2)
,-->下一个状态
先后关系
那么这两个相邻的状态之间是否存在一种关系呢?
求余原理:a%b = k ==> a = b(a/b) +k "/"舍掉余数的除法【int计算机除法】 ==> k=a-(a/b)b
我们知道: a%b = a - (a/b)*b(这里的 “/” 指的是整除,例如 5/2=2 , 1/3=0),
那么,我们可以进一步得到:
gcd = b*x1 + (a-(a/b)*b)*y1
= b*x1 + a*y1 – (a/b)*b*y1
= a*y1 + b*(x1 – a/b*y1) `……(3)`
对比之前我们的状态,式(3)
和式(1)
:求一组 x 和 y 使得:ax + by = gcd ,是否发现了什么?
这里:
x = y1
y = x1 – a/b*y1
现态是x,y 次态是x1,y1 而次态是已知的
这就是`递推式`,注意x,y是递归过程中的`上一层`,x1,y1是`下一层`(下一个状态)得到的值
从最下一层往开始回推 bx1 + (a%b)y1 = gcd (因为找到了gcd)回到观察。
而这样反推回去的是 ax+by=d 的解
而我们要的是 =m的解法 又 因为 m是d(a,b的gcd)的倍数
所以 x*(m/gcd) 乘他们差的倍数
通解
那么通解(t任意是倍数,x加那么y减):
x=x0`+`(b/gcd)*t 所有的x对b同模
y=x0`-`(b/gcd)*t 所有的y对a同模
完整代码及测试
package BlueCup.Six_MathQuestion;
public class 欧几里得算法 {
//中国的辗转相除法 求最大公约自公因子
//4 是 4 8 的 最大公约数
static long x, y;//全局变量存储 xy的推算
public static void main(String[] args) throws Exception {
//ax+by=ans
long ans;
try {
ans = LinearEquation(2, 3, 1);
System.out.println(x + "+" + y + "=" + ans);//2x+3y=1 >x=-1 y=1
ans = LinearEquation(2, 7, 1);
System.out.println(x + "+" + y + "=" + ans);//2x+7y=1 >x=-3 y=1
ans = LinearEquation(12, 42, 6);
System.out.println(x + "+" + y + "=" + ans);//12x+42y=6 >x=-3 y=1
ans = LinearEquation(12, 42, 5);
System.out.println(x + "+" + y + "=" + ans);//无解
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
/**
* 欧几里得算法,既辗转相除法
* 求出最大公约数(公因子)
*/
public static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
/**
* 最小公倍数 lowest common multiple*/
public static long lcm(long a, long b) {
return a * b / gcd(a, b);
}
/**
* 扩展欧几里得算法
* 调用完成后的 xy是ax+by=gcd(a,b)的解*/
public static long ext_gcd(long a, long b) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long res = ext_gcd(b, a % b);
//到最后一层开始递推x,y
//已经最下一次更新了 x0 y0 在b==0时候就初始化了
long x1 = x;//备份
x = y;//更新x
y = x1 - a / b * y;//更新y
// System.out.println(x + " " + y);测试变化
return res;
}
/**
* 线性方程
* ax+by=m 当m是gcd(a,b)的倍数时有解
* 等价于 ax = m mod b*/
public static long LinearEquation(long a, long b, long m) throws Exception {
long d = ext_gcd(a, b);
if (m % d != 0) throw new Exception("无解");//m不是d的倍数无解
long t = m / d;//倍数 m是d的几倍
x *= t;
y *= t;
return d;
}
}
乘法逆元
1.乘法逆元(在维基百科中也叫倒数,当然是 mod p后的,其实就是倒数不是吗?):
如果ax≡1 (mod p),且gcd(a,p)=1(a与p互质),则称a关于模p的乘法逆元为x。
为什么可以用扩展欧几里得求得逆元?
我们都知道模就是余数,比如12%5=12-52=2,18%4=18-44=2。(/是程序运算中的除)
那么ax≡1 (mod p)即ax-yp=1.把y写成+的形式就是ax+py=1,为方便理解下面我们把p写成b就是ax+by=1。
就表示x是a的模b乘法逆元,y是b的模a乘法逆元。然后就可以用扩展欧几里得求了。
知道逆元怎么算之后,那么乘法逆元有什么用呢?
做题时如果结果过大一般都会让你模一个数,确保结果不是很大,而这个数一般是1e9+7,而且这个数又是个素数,
加减乘与模运算的顺序交换不会影响结果,但是除法不行。有的题目要求结果mod一个大质数,如果原本的结果中有除法,比如除以a,那就可以乘以a的逆元替代。
(除一个数等于乘它的倒数,虽然这里的逆元不完全是倒数,但可以这么理解,毕竟乘法逆元就是倒数的扩展)。
结束语
呃,,这个问题我细啃了两天,遇到难题就像放弃, 不过还是咬牙坚持了一下,果然挺过去就是豁然开朗 问题突然变的很简单
一个字 妙啊~!!
还是要相信自己——————想成为大佬的第8天
。上述全是自己一个字一个字梳理码的。记得这么详细 便于自己复习和有需求的朋友理解。 如有问题 欢迎支教!!

练习题
本文地址:https://dxoca.cn/Algorithm/183.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。