Educational Codeforces Round 16 D. Two Arithmetic Progressions

問題

codeforces.com

x = a1 * k + b1 = a2 * l + b2, L <= x <= R を満たす数 x がいくつあるか求めよ。

解法

k, l の組を一つ求められれば, 後は x が lcm(a1, a2) の周期で解になるので簡単です(実装が楽とは言っていない)。

a1 * k + b1 = a2 * l + b2 を変形すると
a1 * k - a2 * l = b2 - b1 となります。

これの解は, 拡張ユークリッドの互除法を使えば求められます。これを使うと
a1 * x + a2 * y = g (g は a1, a2 の最大公約数) という形の x, y, g を求めることができ, 全体を (b2-b1)/g 倍すれば k = x, -l = y となっている, というわけです。

後はめんどくさいですがゴニョゴニョします。
下のコードでは, この後

• k, l を 0 以上に調整する
• x が L 以上になるように調整する
• L <= x <= R となるものの数を求める

というようにやりました。全部二分探索です。

なんか素直に実装すると 10^18 まわりがめんどくさそうなので python で実装しました。
python ってなんかカッコよくかかないといけない感じがしますが下のコードはダサダサです。

def extgcd(a, b):
    x, y = 0, 0
    d = a;
    if b != 0:
        d, y, x = extgcd(b, a%b)
        y -= (a//b) * x
    else:
        x, y = 1, 0
    return (d, x, y)

def main():
    a1, b1, a2, b2, L, R = map(int, input().split())
    # とりあえず k, l の候補を出す
    g, k, l = extgcd(a1, a2);
    b = b2-b1;
    if (b%g != 0):
        print (0)
        return
    k *= b//g
    l *= -b//g
    # k >= 0, l >= 0 を満たすようにする
    low = -2**100
    high = 2**100
    while high-low > 1:
        med = (low+high)//2
        tk = k+med*a2//g
        tl = l+med*a1//g
        if (tk >= 0 and tl >= 0):
            high = med
        else:
            low = med
    k = k+high*a2//g
    # x >= L を満たすようにする
    x = a1*k+b1
    low = -1
    high = 2**100
    lcm = a1*a2//g
    while high - low > 1:
        med = (low+high)//2
        tx = x+med*lcm
        if tx >= L:
            high = med
        else:
            low = med
    x = x+high*lcm
    # x <= R を満たすものの数を求める
    low = 0
    high = 2**100
    while high-low > 1:
        med = (low+high)//2
        tx = x+med*lcm
        if (tx <= R):
            low = med
        else:
            high = med
    if low == 0 and x > R:
        print (0)
        return
    print (low+1)
    return

if __name__=="__main__":
    main()