本文共 649 字，大约阅读时间需要 2 分钟。
这就是简单的扩展欧几里得算法，求x 的最小正整数解
#include#include using namespace std;typedef long long LL;void exgcd(LL a, LL b, LL &x, LL &y){ if(b == 0) { x = 1; y = 0; return ; } exgcd(b, a%b, x, y); LL tmp = x; x = y; y = tmp - ( a / b) * y;}LL gcd(LL m, LL n){ if(n == 0) return m; return gcd(n, m % n);}int main(){ LL a,b,x,y; while(cin >> a >> b) { if(gcd(a, b) != 1) { puts("sorry"); continue; } exgcd(a, b, x, y); x = (b + x % b) % b; y = (1 - a * x) / b; cout<< x << " " << y << endl; } return 0;}
转载地址：http://wvxbx.baihongyu.com/