結果

問題 No.195 フィボナッチ数列の理解(2)
ユーザー gew1fw
提出日時 2025-06-12 15:19:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,968 bytes
コンパイル時間 326 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 413,000 KB
最終ジャッジ日時 2025-06-12 15:19:18
合計ジャッジ時間 5,236 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def find_min_A_B(X, Y, Z):
    max_k = 50
    a = [0] * (max_k + 1)
    b = [0] * (max_k + 1)
    a[1] = 1
    a[2] = 0
    b[1] = 0
    b[2] = 1
    for k in range(3, max_k + 1):
        a[k] = a[k-1] + a[k-2]
        b[k] = b[k-1] + b[k-2]

    candidates = []

    pairs = [(X, Y, Z), (X, Z, Y), (Y, Z, X)]
    for P, Q, R in pairs:
        for k in range(1, max_k + 1):
            a1 = a[k]
            b1 = b[k]
            for m in range(1, max_k + 1):
                a2 = a[m]
                b2 = b[m]
                D = a1 * b2 - a2 * b1
                if D != 0:
                    numerator_A = P * b2 - Q * b1
                    numerator_B = Q * a1 - P * a2
                    if D == 0:
                        continue
                    if numerator_A % D != 0 or numerator_B % D != 0:
                        continue
                    A = numerator_A // D
                    B = numerator_B // D
                    if A <= 0 or B <= 0:
                        continue
                    current = [A, B]
                    found = False
                    if current[0] == R:
                        found = True
                    if current[1] == R:
                        found = True
                    for step in range(2, 50):
                        next_val = current[step-1] + current[step-2]
                        if next_val == R:
                            found = True
                            break
                        if next_val > R:
                            break
                        current.append(next_val)
                    if found:
                        candidates.append((A, B))
                else:
                    if a1 * b2 != a2 * b1:
                        continue
                    if a2 == 0 or b2 == 0:
                        if a1 == 0 or b1 == 0:
                            continue
                    if a2 * P != a1 * Q:
                        continue
                    if b2 * P != b1 * Q:
                        continue
                    a_eq = a1
                    b_eq = b1
                    c_eq = P
                    d = math.gcd(a_eq, b_eq)
                    if c_eq % d != 0:
                        continue
                    a_prime = a_eq // d
                    b_prime = b_eq // d
                    c_prime = c_eq // d
                    g, x, y = extended_gcd(a_prime, b_prime)
                    if g != 1:
                        continue
                    x0 = x * c_prime
                    y0 = y * c_prime
                    if b_prime != 0:
                        t_min = math.ceil((-x0) / b_prime)
                    else:
                        if a_prime != 1:
                            continue
                        if x0 <= 0:
                            continue
                        t_min = -1000000
                        t_max = 1000000
                    if a_prime != 0:
                        t_max = math.floor(y0 / a_prime)
                    else:
                        if b_prime != 1:
                            continue
                        if y0 <= 0:
                            continue
                        t_min = -1000000
                        t_max = 1000000
                    t_min = max(t_min, -1000000)
                    t_max = min(t_max, 1000000)
                    for t in range(t_min, t_max + 1):
                        x_t = x0 + b_prime * t
                        y_t = y0 - a_prime * t
                        if x_t <= 0 or y_t <= 0:
                            continue
                        A = x_t
                        B = y_t
                        current = [A, B]
                        found = False
                        if current[0] == R:
                            found = True
                        if current[1] == R:
                            found = True
                        for step in range(2, 50):
                            next_val = current[step-1] + current[step-2]
                            if next_val == R:
                                found = True
                                break
                            if next_val > R:
                                break
                            current.append(next_val)
                        if found:
                            candidates.append((A, B))
    if not candidates:
        return -1
    min_A = min(c[0] for c in candidates)
    filtered = [c for c in candidates if c[0] == min_A]
    min_B = min(c[1] for c in filtered)
    return (min_A, min_B)

def main():
    X, Y, Z = map(int, input().split())
    result = find_min_A_B(X, Y, Z)
    if result == -1:
        print(-1)
    else:
        print(result[0], result[1])

if __name__ == "__main__":
    main()
0