<span>扩展欧几里得算法</span>
#include <cstdio>
int x, y, a, b;
void exgcd(int a, int b){
if(b == 0) {
x = 1, y = 0;
return ;
}
exgcd(b, a % b);
int xx = x, yy = y;
x = yy;
y = xx - (a / b) * yy;
return ;
}
int main() {
freopen("test.in", "r", stdin);
scanf("%d%d", &a , &b);
exgcd(a, b);
printf("%d", (x %b + b) % b);
return 0;
}
查看8道真题和解析