扩展欧几里得例题(luogu

luo gu

由$a\ast x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}b)$ 推导为扩展欧几里得

->$a\ast x\mathrm{m}\mathrm{o}\mathrm{d}b==1\mathrm{m}\mathrm{o}\mathrm{d}b$->$a\ast x\mathrm{m}\mathrm{o}\mathrm{d}b=1$即-> $a\ast x=n\ast b+1$(n是常数)-> $a\ast x-n\ast b=1$->$a\ast x+y\ast b=1$ (y = -n,常数无影响) 模板： #include <iostream> #include <string.h> #include <queue> 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; }