ここに訳してくれている人がいる。http://d.hatena.ne.jp/kabus/20060728
以下問題の解き方。
x + mt = y + nt (mod L)より、
x + mt = y + nt + kL
(n-m) t + Lk = x - y となるような整数(t, k)の組を見つければいい。（問題では、最小の正の整数t*を求めることになるが、これは求まったtに対する代表元を考えればいい。）
このような解が存在する必要十分条件は、(x-y)がgcd(n-m, L)で割り切れることである。
まず、必要条件の証明。
もし、(x-y)がgcd(n-m, L)で割り切れない場合に、(t, k)が存在したとする。
このとき、
左辺 ≡ 0 (mod gcd(n-m, L))に対して、右辺 > 0 (mod gcd(n-m, L))となり矛盾。よって(x-y)がgcd(n-m, L)で割り切れない場合は、(t, k)の組は存在しない。
次に、十分条件の証明。
両辺をgcd(n-m, L)で割る。
(n-m)/gcd(n-m, L) をA、L/gcd(n-m, L)をB、(x-y)/gcd(n-m, L)をCとおくと、
At + Bk = Cと書ける。このとき、AとBは互いに素なので、Aを法にしたときのBの逆元が存在する。
つまり、y ≡ 1/B (mod A)となるようなyが存在する。
よって、1 - By ≡ 0 (mod A)。これは、(1 - By)がAで割り切れることを意味しているので、
x = (1 - By) / Aとなる整数xが存在する。これを変形すると、Ax + By = 1となり、この式を満たす整数(x, y)が存在する。これを両辺C倍してやると、A(Cx) + B(Cy) = Cとなり、(Cx, Cy)が(t, k)に他ならない。
ということで、解が存在するか否かは、gcdを出すだけで良いです。加えて、(n-m) t + Lk = x - y を満たす(t, k)の組は、(n-m)t' + Lk' = gcd(n-m, L)を満たす(t', k')を拡張ユークリッド互除法で出し、gcd(n-m, L)と(x - y)の比に合わせてスケーリングしなおせばOK。
最後に、問題となるのは、求まったtに対して、それと合同な最小の正の整数t*をどう出すか？そもそも何を法にして考えるか？これは、目盛りがL個付いている時計を(n-m)目盛りずつジャンプしていくと、何回ジャンプすると、同じ場所に戻ってくるかを考えればいいです。L/gcd(L, n-m)が答えです。ということで、tの法(L/gcd(L, n-m))における代表元を出せばOK。
以下回答ソース。
LL extgcd(LL a, LL b, LL &x, LL &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int d = extgcd(b, a%b, y, x);
y -= (a/b) * x;
return d;
}
LL solve(LL x, LL y, LL m, LL n, LL L) {
if (m == n)
return -1;
LL k, t;
LL g = extgcd(n-m, L, k, t);
if ((x-y) % g)
return -1;
LL ans = (x - y) / g * k;
L /= g;
return (ans % L + L) % L;
}
int main() {
LL x, y, m, n, L;
cin >> x >> y >> m >> n >> L;
LL ret = solve(x, y, m, n, L);
if (ret < 0)
puts("Impossible");
else
printf("%I64d\n", ret);
return 0;
}
