結果

問題 No.195 フィボナッチ数列の理解(2)
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:31:12
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,856 bytes
コンパイル時間 326 ms
コンパイル使用メモリ 82,144 KB
実行使用メモリ 849,112 KB
最終ジャッジ日時 2025-04-24 12:32:48
合計ジャッジ時間 5,163 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 1 MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    sys.setrecursionlimit(1 << 25)
    X, Y, Z = map(int, sys.stdin.readline().split())

    # Precompute Fibonacci numbers up to f[45] which is over 1e9
    fib = [0, 1]
    for i in range(2, 46):
        fib.append(fib[i-1] + fib[i-2])

    def get_coefficients(k):
        if k == 1:
            return (1, 0)
        elif k == 2:
            return (0, 1)
        else:
            return (fib[k-2], fib[k-1])

    # Function to generate all possible i for a number x
    def get_indices(x):
        indices = [1, 2]
        max_i = 3
        while max_i < 46 and fib[max_i-1] <= x:
            max_i += 1
        max_i = min(max_i, 45)
        for i in range(3, max_i+1):
            indices.append(i)
        return indices

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

    # Function to check if z is present in the sequence generated by A, B
    def check_z(A, B, z):
        for k in range(1, 100):  # k up to 100 is enough since fib grows exponentially
            if k == 1:
                a, b = 1, 0
            elif k == 2:
                a, b = 0, 1
            else:
                a, b = fib[k-2], fib[k-1]
            current = A * a + B * b
            if current == z:
                return True
            elif current > z:
                break
        return False

    candidates = []

    # Process all pairs: (X,Y), (X,Z), (Y,Z)
    for (x, y, third) in [(X, Y, Z), (X, Z, Y), (Y, Z, X)]:
        x_indices = get_indices(x)
        y_indices = get_indices(y)
        for i in x_indices:
            a_x, b_x = get_coefficients(i)
            for j in y_indices:
                a_y, b_y = get_coefficients(j)
                D = a_x * b_y - a_y * b_x
                if D != 0:
                    numerator_A = x * b_y - y * b_x
                    numerator_B = y * a_x - x * a_y
                    if numerator_A % D != 0 or numerator_B % D != 0:
                        continue
                    A = numerator_A // D
                    B = numerator_B // D
                    if A > 0 and B > 0:
                        if check_z(A, B, third):
                            candidates.append((A, B))
                else:
                    if x != y or i != j:
                        continue
                    a = a_x
                    b = b_x
                    g, x0, y0 = extended_gcd(a, b)
                    if (x % g) != 0:
                        continue
                    x0 *= (x // g)
                    y0 *= (x // g)
                    delta_a = b // g
                    delta_b = a // g
                    min_t = math.ceil((-x0 + 1) / delta_a) if delta_a != 0 else 0
                    max_t = (y0 - 1) // delta_b if delta_b != 0 else 0
                    if delta_a == 0:
                        if x0 <= 0 or y0 <= 0:
                            continue
                        if check_z(x0, y0, third):
                            candidates.append((x0, y0))
                        continue
                    if delta_b == 0:
                        if x0 <= 0 or y0 <= 0:
                            continue
                        if check_z(x0, y0, third):
                            candidates.append((x0, y0))
                        continue
                    min_t = max(min_t, math.ceil(( -x0 ) / delta_a + 1e-9))
                    max_t = min(max_t, (y0 - 1) // delta_b)
                    if min_t > max_t:
                        continue
                    for t in [min_t, max_t]:
                        A_candidate = x0 + delta_a * t
                        B_candidate = y0 - delta_b * t
                        if A_candidate > 0 and B_candidate > 0:
                            if check_z(A_candidate, B_candidate, third):
                                candidates.append((A_candidate, B_candidate))
                    if delta_a > 0 and delta_b > 0:
                        t = ( -x0 ) // delta_a
                        for t in range(min_t, max_t + 1):
                            A_candidate = x0 + delta_a * t
                            B_candidate = y0 - delta_b * t
                            if A_candidate > 0 and B_candidate > 0:
                                if check_z(A_candidate, B_candidate, third):
                                    candidates.append((A_candidate, B_candidate))

    if not candidates:
        print(-1)
        return

    candidates = list(set(candidates))
    candidates.sort(key=lambda x: (x[0], x[1]))
    for a, b in candidates:
        if check_z(a, b, X) and check_z(a, b, Y) and check_z(a, b, Z):
            print(a, b)
            return
    print(-1)

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