题目链接：http://poj.org/problem?id=1061
这道题目做了三次：
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #define LL long long int 6 LL exgcd(LL a, LL b, LL &x, LL &y){ 7 if (b == 0){ 8 x = 1; y = 0; return a; 9 } 10 LL r = exgcd(b, a%b, x, y); 11 LL t = x; x = y; y = t - a / b * y; 12 return r; 13 } 14 LL gcd(LL a, LL b){ 15 return b ==0?a:gcd(b,a%b); 16 } 17 int main(void){ 18 #ifndef ONLINE_JUDGE 19 freopen("poj1061.in", "r", stdin); 20 #endif 21 LL x, y, m, n, L; 22 while (~scanf("%lld%lld%lld%lld%lld", &x,&y,&m,&n,&L)){ 23 LL a = n - m, b = L, c = x - y; 24 LL t, k; 25 LL temp = gcd(a, b); 26 if (c % temp != 0) { 27 printf("Impossible\n"); continue; 28 } 29 a/=temp; b/=temp; c/=temp; 30 exgcd(a,b,t,k); 31 t *= c; 32 LL kk = t/b; 33 t = t-kk*b; 34 if (t<0) t+=b; 35 printf("%lld\n", t); 36 } 37 return 0; 38 }
学习了一下扩展欧几里德，注意，最后求最小正整数解的时候的处理方法，要判断ｔ是不是小于0,如果小于0就再加上ｂ。
总结一下应用扩展欧几里德的方法：
a * x + b * y = c; 求出d = gcd(a, b)，然后再化简一下原来的方程a /= d; b /= d; c /= d;
然后利用 a * x + b * y = 1求出一个解，x0, y0;然后得到了原方程的一个特解: x0 *= d; y0 *= d;
根据方程通解的公式：x = x0 + b * t; y = y0 - a * t; 求出最小的一个x的整数解。方法就是先假设x0 + b * t = 0; 令t1 = x0 / b;
x0 = x0 - b * t1 如果x0小于0,那么x0 += b;否则解就是x0本身。
今天又把这道题目做了一遍，重新学习了一下扩展欧几里德，理解比以前深了一点儿……
上面的代码估计当时是抄的别人的。。
这回自己写，但还是遇到了点儿问题，关键还是有一个细节理解错了，没有真正搞明白。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cctype> 6 #include <stack> 7 #include <queue> 8 #include <cmath> 9 #include <algorithm> 10 #define lson l, m, rt<<1 11 #define rson m+1, r, rt<<1|1 12 using namespace std; 13 typedef long long int LL; 14 const int MAXN = 0x3f3f3f3f; 15 const int MIN = -0x3f3f3f3f; 16 const double eps = 1e-9; 17 18 void exgcd(LL a, LL b, LL &d, LL &x, LL &y){ 19 if (!b){x = 1; y = 0; d = a; return;} 20 LL t; exgcd(b, a%b, d, x, y); 21 t = x; x = y; y = t - a / b * y; 22 } 23 int main(void){ 24 #ifndef ONLINE_JUDGE 25 freopen("poj1061.in", "r", stdin); 26 #endif 27 LL x, y, m, n, L, d; 28 scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &L); 29 LL B = n - m, X, Y, A = x - y; 30 exgcd(B, L, d, X, Y); 31 if (A%d != 0 || m == n) { 32 printf("Impossible\n"); return 0; 33 } 34 LL s = L / d; 35 X = X * A / d; X = (X%s + s) % s; 36 printf("%lld\n", X); 37 38 return 0; 39 }
注意34行，因为扩展欧几里得求出的一个解X不是最小解，但是属于一个模s的剩余系，所以要进行35行的处理。当初就是这里没有搞清楚。
明显赶脚这次写的过程中比以前好多了，~↖(^ω^)↗
唉，以前写的太挫了……今天复习了一下扩展欧几里德，重写了一遍。感觉比以前写的更精简了，理解更深入了一点。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cctype> 6 #include <stack> 7 #include <queue> 8 #include <map> 9 #include <set> 10 #include <vector> 11 #include <cmath> 12 #include <algorithm> 13 #define lson l, m, rt<<1 14 #define rson m+1, r, rt<<1|1 15 using namespace std; 16 typedef long long int LL; 17 const int MAXN = 0x3f3f3f3f; 18 const int MIN = -0x3f3f3f3f; 19 const double eps = 1e-9; 20 const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1}, 21 {1,1},{1,-1},{-1,-1}}; 22 23 void exgcd(LL a, LL b, LL &d, LL &x, LL &y){ 24 if (!b){ 25 x = 1; y = 0; d = a; return; 26 } 27 else{ 28 exgcd(b, a % b, d, x, y); 29 LL tem = x; x = y; y = tem - (a / b) * y; 30 } 31 } 32 33 int main(void){ 34 #ifndef ONLINE_JUDGE 35 freopen("poj1061.in", "r", stdin); 36 #endif 37 LL x1, y1, m, n, l, a, b, c, d, x, y; 38 cin >> x1 >> y1 >> m >> n >> l; 39 a = n - m; b = l; c = x1 - y1; 40 exgcd(a, b, d, x, y); 41 if (m == n || c % d){ 42 cout << "Impossible\n"; return 0; 43 } 44 x *= c / d; 45 x = (x % l + l) % l; 46 cout << x << endl; 47 48 return 0; 49 }
注意理解第45行。
思路：
(mt + x) 同余于 (nt + y) 模 L 。所以可以得到方程：(n - m) * t + L * k = x - y; 用 exgcd求解，得到一个 (n - m) * t + L * k = gcd(n - m, L) 的一个解x，然后，x *= (x-y) / gcd(n - m, L) 得到的 x 就是原方程的一个解，但是要求最小的正整数 t ，由于原方程有 gcd(n-m, L) 个模 L 不同余的解，并且这些解同属于模 L 的剩余系，所以 x = (x % L + L ) % L ；就得到最小的解。
感觉以前写的太挫了……