对于扩展欧几里得主要部分说明:
1. d' = bx'+(a mod b)y', d' = gcd(b, a mod b);
设 d = gcd(a, b), 因为 d = d', 所以
d = d' = bx'+(a mod b)y' = bx' + (a-floor(a/b)*b)y' = ay'+b(x'-floor(a/b)y');
故有迭代:
x = y'; y = x'-floor(a/b)y';
对于解方程主要部分说明:
1.首先给出两个定理(证明请查看相关数论书):
A. 方程 ax = b (mod n) 有解, 当且仅当 gcd(a, n) | b;
B. 方程 ax = b (mod n) 有d个不同的解, 其中 d = gcd(a, n);
2.证明方程有一解是: x0 = x'(b/d) mod n;
由 a*x0 = a*x'(b/d) (mod n)
a*x0 = d (b/d) (mod n) (由于 ax' = d (mod n))
= b (mod n)
证明方程有d个解: xi = x0 + i*(n/d) (mod n);
由 a*xi (mod n) = a * (x0 + i*(n/d)) (mod n)
= (a*x0+a*i*(n/d)) (mod n)
= a * x0 (mod n) (由于 d | a)
= b
代码如下:
#include <iostream>
#include <cmath>
using namespace std;
int egcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1; y = 0;
return a;
} else {
int tx, ty, d;
d = egcd(b, a%b, tx, ty);
x = ty; y = tx-a/b*ty;
return d;
}
}
void mels(int a, int b, int n) {
int tx, ty, d, x0, i;
d = egcd(a, n, tx, ty);
if (b%d==0) {
x0 = ((tx*b/d)%n+n)%n;
for (i=0; i<d; i++) {
printf("%d ", (x0+i*n/d)%n);
}
} else {
printf("No solutions!");
}
printf("\n");
}
int main() {
mels(14, 30, 100);
return 0;
}
posted on 2007-08-27 11:14
豪 阅读(2169)
评论(2) 编辑 收藏 引用 所属分类:
算法&ACM