扩展欧几里得（递推实现）

#include <iostream>#include <cstdio>#define maxn 1000#define INF 0xfffffffusing namespace std;int m = 0, n = 0;int gcd = 0;int x[maxn], y[maxn], q[maxn];void extend_gcd(){    x[1] = 1;    y[1] = -q[0];    x[2] = -q[1];    y[2] = 1+q[0]*q[1];    for(int i = 2; i < INF; i++){        x[i+1] = x[i-1] - q[i]*x[i];        y[i+1] = y[i-1] - q[i]*y[i];        if(gcd == m*x[i+1] + n*y[i+1]){            printf("m = %d, n = %d\n", m, n);            printf("%d = %d*(%d) + %d*(%d)\n", gcd, m, x[i+1], n, y[i+1]);            break;        }    }}int init(){    int r = 1, i = 0, t;    int a = m, b = n;    memset(x, 0, sizeof(x));    memset(y, 0, sizeof(y));    memset(q, 0, sizeof(q));    while(r){        r = a%b;        t = a/b;        q[i++] = t;        a = b;        b = r;    }    return a;}int main(){    int temp;    while(scanf("%d%d", &m, &n)!=EOF){        if(m < n) { temp = m, m = n, n = temp; }        gcd = init();        if(m && n){//此处只是考虑都不为零的情况。            extend_gcd();        }    }    return 0;}

3楼oraclebea前天 22:39

这个求逆元的时候用到过。

2楼wangwenhao00前天 22:38

欢迎浏览，交流。多多指正。我的QQ：1530168830.

1楼wangwenhao00前天 15:01

嗯嗯。