結果

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

ソースコード

diff # 

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

    # Precompute Fibonacci numbers up to a large value
    fib = [1, 1]
    while True:
        next_fib = fib[-1] + fib[-2]
        if next_fib > 1e18:
            break
        fib.append(next_fib)

    def get_candidates(n):
        candidates = []
        # k=1: A =n
        candidates.append((1, 1, 0, n))
        # k=2: B =n
        candidates.append((2, 0, 1, n))
        # k >=3:
        for k in range(3, len(fib) + 2):
            if (k - 3) >= len(fib) or (k - 2) >= len(fib):
                break
            a = fib[k - 3]
            b = fib[k - 2]
            if a + b > n:
                continue
            candidates.append((k, a, b, n))
        return candidates

    x_candidates = get_candidates(X)
    y_candidates = get_candidates(Y)

    solutions = []

    def is_in_sequence(A, B, target):
        if A == target or B == target:
            return True
        prev, current = A, B
        while True:
            next_val = prev + current
            if next_val == target:
                return True
            if next_val > target:
                return False
            prev, current = current, next_val

    from itertools import product

    for x_cand, y_cand in product(x_candidates, y_candidates):
        kx, ax, bx, rx = x_cand
        ky, ay, by, ry = y_cand

        D = ax * by - ay * bx

        if D != 0:
            numerator_A = rx * by - ry * bx
            numerator_B = ry * ax - rx * ay
            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
            if is_in_sequence(A, B, Z):
                solutions.append((A, B))
        else:
            if ax * by != ay * bx:
                continue
            if rx * by != ry * bx:
                continue
            if ax * ry != ay * rx:
                continue

            def find_solutions(a, b, r):
                sols = []
                if a == 0 and b == 0:
                    return []
                if a == 0:
                    if r % b != 0:
                        return []
                    B_val = r // b
                    if B_val > 0:
                        return [(1, B_val)]
                    else:
                        return []
                if b == 0:
                    if r % a != 0:
                        return []
                    A_val = r // a
                    if A_val > 0:
                        return [(A_val, 1)]
                    else:
                        return []
                max_A = (r - b) // a
                if max_A < 1:
                    max_B = (r - a) // b
                    if max_B < 1:
                        return []
                    for B_val in range(1, max_B + 1):
                            rem = r - b * B_val
                            if rem <= 0:
                                continue
                            if rem % a != 0:
                                continue
                            A_val = rem // a
                            if A_val >= 1:
                                sols.append((A_val, B_val))
                else:
                    for A_val in range(1, max_A + 1):
                        rem = r - a * A_val
                        if rem <= 0:
                            continue
                        if rem % b != 0:
                            continue
                        B_val = rem // b
                        if B_val >= 1:
                            sols.append((A_val, B_val))
                return sols

            sols = find_solutions(ax, bx, rx)
            for A, B in sols:
                if ay * A + by * B != ry:
                    continue
                if is_in_sequence(A, B, Z):
                    solutions.append((A, B))

    if not solutions:
        print(-1)
        return

    solutions.sort(key=lambda x: (x[0], x[1]))
    print(solutions[0][0], solutions[0][1])

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