【扩展欧几里德】POJ 1061 + zoj 2657【更新时间2011-11-18】
http://poj.org/problem?id=1061http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1657
两题一模一样，只是无解时输出情况不同
首先由题意有【x+ms与y+ns建立等价关系,设次数为s】：
x+ms ≡ (y+ns)(mol L)
->(x+ms)%L = (y+ns)%L
->((x+ms) - (y+ns))%L = 0
->(x+ms) - (y+ns) = k*L
化简得：
k*L + (n-m)*s = x-y
令a = L，b = n-m，n = x-y得
ak + bs = n;[其中k，s为未知数，形如ax + by = n
Egcd解析：
http://dl.iteye.com/upload/attachment/531208/565a1d2f-6c6f-38f3-a10b-f648684dbd3f.png
解方程步骤：
①：令d = gcd(a, b)
②：若n%d != 0，则无解
③：方程两边同时除以d ，得到a'k + b's = n'
④：用扩展欧几里德Egcd求出a'k + b's = 1的解s
⑤：得到的就是方程的一组解
⑥：得到最小非负整数解，模a+a模a【求b的模a，求a的模b, 为什么？自己想】
#include <iostream>#include <algorithm>#include <string>//#include <map>#include <queue>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>//#include <ctime>#include <ctype.h>using namespace std;#define LL long long#define inf 0x3fffffffLL gcd (LL a, LL b){return b ? gcd (b, a%b) : a;}void Egcd (LL a, LL b, LL &x, LL &y){if (b == 0){x = 1, y = 0;return ;}Egcd (b, a%b, x, y);LL tp = x;x = y;y = tp - a/b*y;}int main(){LL xx, yy, a, b, x, y, L, n, M, N, d;while (~scanf ("%lld%lld%lld%lld%lld", &xx, &yy, &M, &N, &L)){a = L;b = N - M;n = xx - yy;d = gcd (a, b);if (n % d != 0){puts ("Impossible");continue;}a /= d;b /= d;n /= d;Egcd (a, b, x, y);y *= n;if (a < 0) a = -a; //周期是正的y = (y % a + a) % a;printf ("%lld\n", y);}return 0;}
页:
[1]