扩展欧几里得例题(luogu_1082) 扩展欧几里得例题(luogu_1082)

【扩展欧几里得例题(luogu_1082)】luo gu
由 a ? x ≡ 1 ( m o d b ) a*x \equiv1 (\mod b) a?x≡1(modb) 推导为扩展欧几里得

-> a ? x m o d b = = 1 m o d b a*x \mod b == 1 \mod b a?xmodb==1modb
-> a ? x m o d b = 1 a*x \mod b =1 a?xmodb=1
即->a ? x = n ? b + 1 a*x = n*b+1 a?x=n?b+1(n是常数)
->a ? x ? n ? b = 1 a*x-n*b=1 a?x?n?b=1
-> a ? x + y ? b = 1 a*x+y*b=1 a?x+y?b=1 (y = -n,常数无影响)
模板：

#include #include #include using namespace std; int exgcd(int a,int b,long long & x,long long & y) { if (b == 0) { x = 1; y = 0; return a; } int res = exgcd(b,a%b,x,y); // 回溯的时候进行推倒x,y long long temp = y; y = x - (a/b)*y; x = temp; return res; }int main() { int a,b; long long x,y; cin >> a >> b; exgcd(a,b,x,y); if (x > 0) { while (x > 0) x -= abs(b); x += abs(b); cout << x << endl; } else { while (x < 0) x += abs(b); cout << x << endl; } return 0; }