３．求解同余方程
/* * 扩展欧几里得算法(extended Euclidean algorithm) * 扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： * ax+by = gcd(a, b) = d（解一定存在，根据数论中的相关定理）。 * 扩展欧几里德常用在求解模线性方程及方程组中。 * */#include// 递归法实现扩展欧几里德算法long exgcd1(long a, long b, long *x, long *y){ if(b==0) { *x=1; *y=0; return a; } long r = exgcd1(b, a%b, x, y); long t = *x; *x = *y; *y = t - a / b * *y; return r;}// 递推法实现扩展欧几里德算法（正解）long exgcd2(long a, long b, long *x, long *y){ long x0=1, y0=0, x1=0, y1=1; long r, q; *x=0; *y=1; r = a % b; q = (a - r) / b; while(r) { *x = x0 - q * x1; *y = y0 - q * y1; x0 = x1; y0 = y1; x1 = *x; y1 = *y; a = b; b = r; r = a % b; q = (a - r) / b; } return b;}int main(void){ long x, y; printf("a=%d, b=%d, x=%ld, y=%ld exgcd=%ld\n", 42, 70, x, y, exgcd1(42, 70, &x, &y)); printf("a=%d, b=%d, x=%ld, y=%ld exgcd=%ld\n", 42, 70, x, y, exgcd2(42, 70, &x, &y)); return 0;}
关键代码（正解）：
// 递推法实现扩展欧几里德算法（正解）long exgcd2(long a, long b, long *x, long *y){ long x0=1, y0=0, x1=0, y1=1; long r, q; *x=0; *y=1; r = a % b; q = (a - r) / b; while(r) { *x = x0 - q * x1; *y = y0 - q * y1; x0 = x1; y0 = y1; x1 = *x; y1 = *y; a = b; b = r; r = a % b; q = (a - r) / b; } return b;}