文章目录
欧几里得算法（辗转相除法）
欧几里得算法是用于求最大公约数
任何一个数a都可以表示成
a=pb+r
如果r=0则b就是其最大公约数
如果r！=0，就转化为b，r的
a,q,p,r均为整数
gcd表示最大公约数
gcd(a,b)=gcd(b,r)=gcd(b,a%b)
因此结束条件就是r=0，即b=0
typedef long long ll; //最大公约数 int gcd(int a, int b) { return b==0?a:gcd(b, a % b); }
最小公倍数
我们知道a和b的最小公倍数是a和b的乘积除以gcd（a，b）
但是我们如果用两数相乘的话有可能会溢出
//最小公倍数a*b/gcd（a，b），为了避免溢出应该用a/gcd（a，b）*b int lcm(int a, int b)// { return a / gcd(a, b) * b; }
贝祖定理
ax+by称a，b的线性组合，
ax+by=m有解，当且仅当m为gcd（a，b）的倍数
ax+by=1时，说明a，b互质
如8和12的最大公约数是4
8x+12y=4,x=-1,y=1为其的一组解
扩展欧几里得算法
ll exgcd(ll a, ll b, ll& x, ll& y)//通过计算出gcd求得解 { if (b == 0ll) { //此时ax+by=g //gcd=a //x=1,y=0/1/2………任意数 //x=1,y=0为其中的一组解 x = 1; y = 0; return a;//到达递归边界开始向上一层返回 } //gcd（a，b）=gcd(b,a%b) ll x1=0, y1=0; ll g = exgcd(b, a % b, x1, y1);//最大公约数,g为最大公约数 //b*x1+(a%b)*y1=gcd(b,a%b)=gcd(a,b); //(x1,y1)->(x,y) x = y1;//x等于上一轮的y1 y = x1 - (a / b) * y1; return g;//g就是最大公约数 }
int main() { ll a, b; while (cin >> a >> b) { //先判断是否有解 //（a，b），的最大公约数为1,有解 if (gcd(a, b) != 1ll)//无解，不为互质数 { cout << "sorry" << endl; continue; } ll x, y;//x和y就是解 //求ax+by的一组解,用引用传就可以把x和y给解出来 ll g = exgcd(a, b, x, y); //x = (x % b + b) % b;//以正数形式表现 cout <<"x=" << x << " y=" << y << endl; } return 0; }
