結果

問題 No.2259 Gas Station
ユーザー lam6er
提出日時 2025-03-20 20:42:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 1,685 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 61,076 KB
最終ジャッジ日時 2025-03-20 20:42:38
合計ジャッジ時間 2,163 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def find_min_change(L, R, C):
    # Step 1: Check if there is any x in [L, R] such that Cx is divisible by 1000
    d = math.gcd(C, 1000)
    step = 1000 // d
    first_multiple = ((L + step - 1) // step) * step
    if first_multiple <= R:
        return 0

    # Step 2: Find the maximum (Cx mod 1000) for x in [L, R]
    A = C % 1000
    if A == 0:
        # Already handled by step 1
        return 0

    d_gcd = math.gcd(A, 1000)
    m = 1000
    max_mod = -1

    max_i = (1000 // d_gcd) - 1  # since k = m - d_gcd*i should be positive
    for i in range(1, max_i + 1):
        k = m - d_gcd * i
        a = A // d_gcd
        m_div_d = m // d_gcd
        k_div_d = k // d_gcd

        # Solve a * x ≡ k_div_d mod m_div_d
        try:
            inv_a = pow(a, -1, m_div_d)
        except ValueError:
            # This should not happen as a and m_div_d are coprime
            continue

        s = (k_div_d * inv_a) % m_div_d
        s_mod = s % m_div_d

        # Calculate t_min and t_max
        t_min = (L - s_mod + m_div_d - 1) // m_div_d
        t_max = (R - s_mod) // m_div_d

        if t_min <= t_max and t_max >= 0:
            max_mod = k
            break

    if max_mod == -1:
        # Fallback to check all x in [L, R], but ideally should not reach here
        max_mod_val = 0
        for x in [L, R]:
            mod = (x * C) % 1000
            if mod != 0:
                mod = 1000 - mod
            if mod > max_mod_val:
                max_mod_val = mod
        return 1000 - max_mod_val if max_mod_val != 0 else 0
    else:
        return 1000 - max_mod

# Read input
L, R, C = map(int, input().split())
print(find_min_change(L, R, C))
0