扩展欧几里得（递推实现）
#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;}