結果
| 問題 |
No.195 フィボナッチ数列の理解(2)
|
| コンテスト | |
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 20:28:30 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 8,327 bytes |
| コンパイル時間 | 202 ms |
| コンパイル使用メモリ | 82,560 KB |
| 実行使用メモリ | 852,448 KB |
| 最終ジャッジ日時 | 2025-06-12 20:28:39 |
| 合計ジャッジ時間 | 6,098 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | AC * 1 MLE * 1 -- * 20 |
ソースコード
import math
def main():
X, Y, Z = map(int, input().split())
fib = [0] * 60
fib[0] = 0
fib[1] = 1
for i in range(2, 60):
fib[i] = fib[i-1] + fib[i-2]
candidates = []
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)
for u in [X, Y, Z]:
for v in [X, Y, Z]:
if u == v:
pair_list = [(u, v)]
else:
pair_list = [(u, v), (v, u)]
for (curr_u, curr_v) in pair_list:
for i in range(1, 60):
for j in range(1, 60):
a1 = fib[i-2] if i >= 2 else 0
b1 = fib[i-1]
a2 = fib[j-2] if j >= 2 else 0
b2 = fib[j-1]
D = a1 * b2 - a2 * b1
if D != 0:
numerator_A = curr_u * b2 - curr_v * b1
numerator_B = curr_v * a1 - curr_u * a2
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
third = None
if curr_u == X and curr_v == Y:
third = Z
elif curr_u == X and curr_v == Z:
third = Y
elif curr_u == Y and curr_v == X:
third = Z
elif curr_u == Y and curr_v == Z:
third = X
elif curr_u == Z and curr_v == X:
third = Y
elif curr_u == Z and curr_v == Y:
third = X
terms = set()
a, b = A, B
terms.add(a)
terms.add(b)
max_term = max(X, Y, Z)
next_term = a + b
limit = max_term * 2
while next_term <= limit:
terms.add(next_term)
a, b = b, next_term
next_term = a + b
if (X in terms) and (Y in terms) and (Z in terms):
candidates.append((A, B))
else:
if curr_u * a2 != curr_v * a1 or curr_u * b2 != curr_v * b1:
continue
a1_orig = a1
b1_orig = b1
u_orig = curr_u
a1 = a1_orig
b1 = b1_orig
u = u_orig
if a1 == 0 and b1 == 0:
continue
if a1 == 0:
if b1 == 0:
continue
if u % b1 != 0:
continue
B_val = u // b1
if B_val <= 0:
continue
A = 1
B = B_val
third = None
if curr_u == X and curr_v == Y:
third = Z
elif curr_u == X and curr_v == Z:
third = Y
elif curr_u == Y and curr_v == X:
third = Z
elif curr_u == Y and curr_v == Z:
third = X
elif curr_u == Z and curr_v == X:
third = Y
elif curr_u == Z and curr_v == Y:
third = X
terms = set()
a, b = A, B
terms.add(a)
terms.add(b)
max_term = max(X, Y, Z)
next_term = a + b
limit = max_term * 2
while next_term <= limit:
terms.add(next_term)
a, b = b, next_term
next_term = a + b
if (X in terms) and (Y in terms) and (Z in terms):
candidates.append((A, B))
else:
d = math.gcd(a1, b1)
if u % d != 0:
continue
a1_div = a1 // d
b1_div = b1 // d
u_div = u // d
g, x_gcd, y_gcd = extended_gcd(a1_div, b1_div)
x0 = x_gcd * u_div
y0 = y_gcd * u_div
t_min = math.ceil(-x0 / b1_div) if b1_div != 0 else -10**18
t_max = math.floor(y0 / a1_div) if a1_div != 0 else 10**18
if b1_div == 0:
t_min = -10**18
if a1_div == 0:
t_max = 10**18
if t_min > t_max:
continue
for t in range(t_min, t_max + 1):
A_candidate = x0 + b1_div * t
B_candidate = y0 - a1_div * t
if A_candidate <= 0 or B_candidate <= 0:
continue
third = None
if curr_u == X and curr_v == Y:
third = Z
elif curr_u == X and curr_v == Z:
third = Y
elif curr_u == Y and curr_v == X:
third = Z
elif curr_u == Y and curr_v == Z:
third = X
elif curr_u == Z and curr_v == X:
third = Y
elif curr_u == Z and curr_v == Y:
third = X
terms = set()
a, b = A_candidate, B_candidate
terms.add(a)
terms.add(b)
max_term = max(X, Y, Z)
next_term = a + b
limit = max_term * 2
while next_term <= limit:
terms.add(next_term)
a, b = b, next_term
next_term = a + b
if (X in terms) and (Y in terms) and (Z in terms):
candidates.append((A_candidate, B_candidate))
if not candidates:
print(-1)
return
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)
result = None
for c in filtered:
if c[1] == min_b:
result = c
break
print(result[0], result[1])
if __name__ == '__main__':
main()