欧几里得算法
裴蜀定理
对于给定的正整数a,b方程ax+by=c有解的充要条件为c是gcd(a,b)的整数倍
扩展欧几里得
#include<iostream> #include<algorithm> using namespace std; int exgcd(int a,int b,int &x,int &y){ if(!b){ x = 1,y =0; return a; } int d = exgcd(b,a % b,y,x); y -= a / b * x; return d; } int main(){ int t;cin >> t; while(t--){ int a, b, x, y; cin >> a >> b; exgcd(a,b,x,y); cout << x << " " << y << endl; } return 0; }
①求逆元
前提：g c d ( a , b ) = 1
逆元的定义：若a ∗ x ≡ 1 ( m o d b ) 且a与b互质，那么x为a的逆元
上式可以变形成为：a∗x=by+1 ⇨a ∗ x + b ∗ y = 1 所以通过exgcd(a,b,x,y)求出的x即为a的乘法逆元
②求线性同余方程
