一.贝祖等式
给定a，b均为整数，一定存在一组整数x，y使得a，b满足a*x + b*y = gcd(a，b) = c。
而拓展欧几里得算法就是求出这组整数(x，y)的算法。
二.拓展欧几里得算法
首先先回顾一下欧几里得算法，欧几里得算法是计算两个数最大公因数的计算方法，如果要求gcd(a，b)的话，可以不断将其变为gcd(b，a%b)，一直到b为0，此时的a就是最大公因数。用c表示gcd(a，b)的值，就可以写成gcd(c，0)。
我们不难发现，此时x和y的值是容易找的，即当x= 1，y=0时满足x*c+ y*0 = gcd(a，b) = c。那么我们可以从后向前推，假设已知一对(x，y)可以使得x*b+y*(a%b) = gcd(a，b)，能否求得新的一对x，y使得a，b满足x*a + y*b = gcd(a，b)呢？
a%b可以表示为a-k*b(k=a/b)那么有x*a + y*(a-kb) = gcd(a，b)，展开括号我们可以算出来有y*a + (x-ky)*b = gcd(a，b)。
代码如下：
标签：a%,gcd,欧几里得,整数,蓝桥,算法,公因数,通关 From： https://blog.csdn.net/2301_81317457/article/details/142900599