蛙逢引 ～一次不定式で愛を探す～

蛙が逢引するロマンティックな問題。この問題は、問題文的にも、内容的にも好きだ。

http://poj.org/problem?id=1061

ここに訳してくれている人がいる。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。

以下回答ソース。

view plainprint?

1. LL extgcd(LL a, LL b, LL &x, LL &y) {  
2.     if (b == 0) {  
3.         x = 1;  
4.         y = 0;  
5.         return a;  
6.     }  
7.   
8.     int d = extgcd(b, a%b, y, x);  
9.     y -= (a/b) * x;  
10.     return d;  
11. }  
12.   
13. LL solve(LL x, LL y, LL m, LL n, LL L) {  
14.     if (m == n)  
15.         return -1;  
16.   
17.     LL k, t;  
18.     LL g = extgcd(n-m, L, k, t);  
19.     if ((x-y) % g)  
20.         return -1;  
21.   
22.     LL ans = (x - y) / g * k;  
23.     L /= g;  
24.   
25.     return (ans % L + L) % L;  
26. }  
27.   
28. int main() {  
29.     LL x, y, m, n, L;  
30.   
31.     cin >> x >> y >> m >> n >> L;  
32.   
33.     LL ret = solve(x, y, m, n, L);  
34.     if (ret < 0)  
35.         puts("Impossible");  
36.     else  
37.         printf("%I64d\n", ret);  
38.   
39.     return 0;  
40. }  

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;
}