結果
| 問題 |
No.195 フィボナッチ数列の理解(2)
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:24:01 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 79 ms / 5,000 ms |
| コード長 | 9,094 bytes |
| コンパイル時間 | 197 ms |
| コンパイル使用メモリ | 82,348 KB |
| 実行使用メモリ | 76,988 KB |
| 最終ジャッジ日時 | 2025-05-14 13:25:23 |
| 合計ジャッジ時間 | 2,852 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 22 |
ソースコード
import math
# Extended Euclidean Algorithm: ax + by = gcd(a,b)
# Returns (g, x, y) where g = gcd(a,b) and ax + by = g
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
d, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return d, x, y
def solve():
X, Y, Z = map(int, input().split())
distinct_target_values = sorted(list(set([X, Y, Z])))
# Max k for F_AB(k). F_std(46) ~ 1.8e9, F_std(47) ~ 2.9e9.
# So k up to about 47 should be enough.
N_MAX_K_INDEX = 47
# Precompute standard Fibonacci numbers: F_std[0]=0, F_std[1]=1, ...
# Need up to F_std[N_MAX_K_INDEX-1] for coefficients.
# fib_std array will have size N_MAX_K_INDEX, storing F_std[0]...F_std[N_MAX_K_INDEX-1]
# Or size N_MAX_K_INDEX+1 to store up to F_std[N_MAX_K_INDEX] if k can be N_MAX_K_INDEX+1
# Coefficients are F_std(k-2), F_std(k-1). If max k is N_MAX_K_INDEX, max index needed is N_MAX_K_INDEX-1.
fib_std = [0] * (N_MAX_K_INDEX + 1) # Store F_std[0] to F_std[N_MAX_K_INDEX]
if N_MAX_K_INDEX >=0: fib_std[0] = 0
if N_MAX_K_INDEX >=1: fib_std[1] = 1
for i in range(2, N_MAX_K_INDEX + 1):
fib_std[i] = fib_std[i-1] + fib_std[i-2]
# Get coefficients (cA, cB) for F_AB(k) = cA*A + cB*B
def get_coeffs(k_idx):
if k_idx == 1: return 1, 0
if k_idx == 2: return 0, 1
# For k >= 3, F_AB(k) = F_std(k-2)*A + F_std(k-1)*B
# Check if indices k-2, k-1 are valid for precomputed fib_std
if k_idx < 3 or k_idx - 1 > N_MAX_K_INDEX :
return float('inf'), float('inf') # Invalid k or out of bounds for fib_std
return fib_std[k_idx-2], fib_std[k_idx-1]
min_A_sol, min_B_sol = -1, -1
candidate_AB_pairs = []
# Part 1: Two points define A, B
for k1 in range(1, N_MAX_K_INDEX + 1):
for k2 in range(1, N_MAX_K_INDEX + 1):
if k1 == k2: continue
cA1, cB1 = get_coeffs(k1)
cA2, cB2 = get_coeffs(k2)
if cA1 == float('inf') or cA2 == float('inf'): continue
for val1 in distinct_target_values:
for val2 in distinct_target_values:
D = cA1 * cB2 - cA2 * cB1
if D == 0: continue
A_num = val1 * cB2 - val2 * cB1
B_num = cA1 * val2 - cA2 * val1
if A_num % D == 0 and B_num % D == 0:
A = A_num // D
B = B_num // D
if A > 0 and B > 0:
candidate_AB_pairs.append((A, B))
# Part 2: One point defines A, B (Diophantine equation)
for k_idx in range(1, N_MAX_K_INDEX + 1):
for val_target in distinct_target_values:
cA, cB = get_coeffs(k_idx)
if cA == float('inf'): continue # k_idx invalid or too large
if k_idx == 1: # A = val_target
A, B = val_target, 1
if A > 0: candidate_AB_pairs.append((A,B))
elif k_idx == 2: # B = val_target
A, B = 1, val_target
if B > 0: candidate_AB_pairs.append((A,B))
else: # cA*A + cB*B = val_target. cA, cB >= 1 for k>=3.
g, x0, y0 = extended_gcd(cA, cB)
if val_target % g != 0: continue
A_p = x0 * (val_target // g)
B_p = y0 * (val_target // g)
term_B_for_A_update = cB // g # Coefficient for t in A_s = A_p + t * term_B_for_A_update
term_A_for_B_update = cA // g # Coefficient for t in B_s = B_p - t * term_A_for_B_update
# We need A_s = A_p + t*term_B_for_A_update >= 1
# We need B_s = B_p - t*term_A_for_B_update >= 1
# term_B_for_A_update = F_std(k-1)/g > 0 for k>=3
# term_A_for_B_update = F_std(k-2)/g > 0 for k>=3 (F_std(1)=1)
# t >= (1 - A_p) / term_B_for_A_update
t_min_for_A_cond = math.ceil((1 - A_p) / term_B_for_A_update)
# t <= (B_p - 1) / term_A_for_B_update
t_max_for_B_cond = math.floor((B_p - 1) / term_A_for_B_update)
if t_min_for_A_cond <= t_max_for_B_cond:
# Valid range for t exists. To minimize A, pick t = t_min_for_A_cond.
t = t_min_for_A_cond
A = A_p + t * term_B_for_A_update
B = B_p - t * term_A_for_B_update
if A > 0 and B > 0:
candidate_AB_pairs.append((A, B))
if not candidate_AB_pairs and (min_A_sol == -1) : # Check if list is empty and no solution yet
print("-1")
return
candidate_AB_pairs = sorted(list(set(candidate_AB_pairs)))
max_val_XYZ = max(X,Y,Z)
for A_cand, B_cand in candidate_AB_pairs:
generated_terms = set()
_f1, _f2 = A_cand, B_cand
# Generate terms and add to set
# Stop if terms grow too large or after N_MAX_K_INDEX iterations
for i in range(N_MAX_K_INDEX + 2): # Iterate a bit more than max_k
if i == 0: current_term = _f1
elif i == 1: current_term = _f2
else:
_f_next = _f1 + _f2
_f1 = _f2
_f2 = _f_next
current_term = _f1 # This is F(i-1+1) = F(i) if loop index is i
# After update, _f1 holds F(i+1) using 0-indexed loop
# Correct: term added should be the first term of the pair.
# Iter 0: add A. Iter 1: add B. Iter 2: add A+B.
# To match F_AB(i+1) structure if loop index `i` is 0-based count of steps
# i=0: current_term = A_cand = F_AB(1)
# i=1: current_term = B_cand = F_AB(2)
# i=2: _f_next = A_cand+B_cand. _f1 becomes B_cand, _f2 becomes A_cand+B_cand. Current_term = _f1 (B_cand). This is wrong.
# Let's fix sequence generation:
if i == 0: term_to_add = A_cand
elif i == 1: term_to_add = B_cand
else: # i >= 2
# At this point, _f1 = F_AB(i), _f2 = F_AB(i+1)
# We want to add F_AB(i+1)
# Previous state: _f1 was F_AB(i-1), _f2 was F_AB(i)
# New term is _f1 + _f2 (old values) = F_AB(i+1)
# if i=2, new term is A+B = F_AB(3)
if i==2: _f1, _f2 = A_cand, B_cand # Reset _f1, _f2 for calculating F(3) onwards
next_val = _f1 + _f2
_f1 = _f2
_f2 = next_val
term_to_add = _f1 # This is F_AB(i) as _f1 stores the (i-1)th term for next F(i) calc
# e.g., after first A+B, _f1=B, _f2=A+B. F_AB(3) = A+B added using _f1 of next step.
# This means for loop i, we add F_AB(i+1)
# More simply:
# f_list = [A_cand, B_cand]
# generated_terms.add(A_cand)
# generated_terms.add(B_cand)
# loop: f_new = f_list[-1]+f_list[-2]; f_list.append(f_new); generated_terms.add(f_new)
if term_to_add > max_val_XYZ + abs(B_cand) + abs(A_cand) and term_to_add not in [X,Y,Z]: # Heuristic margin
# If A_cand, B_cand are large, max_val_XYZ could be small. Sums can exceed quickly.
# A better bound for breaking is if term_to_add > max_val_XYZ and all X,Y,Z < term_to_add
pass # The loop limit N_MAX_K_INDEX + 2 is the primary stop
generated_terms.add(term_to_add)
if term_to_add > 2 * 10**9 : break # Hard stop for very large terms / overflow
# After generating sequence (or part of it):
# Check if X, Y, Z are all in generated_terms
# Reset for actual generation:
generated_terms_check = set()
curr1, curr2 = A_cand, B_cand
for _ in range(N_MAX_K_INDEX + 2): # Max relevant terms
if curr1 > max_val_XYZ * 2 + max(A_cand,B_cand) and curr1 not in [X,Y,Z]: # Heuristic bound for adding
break # Optimization if terms grow way too large
generated_terms_check.add(curr1)
if curr1 > 2.1 * 10**9: break # Safety break
curr_next = curr1 + curr2
curr1 = curr2
curr2 = curr_next
found_X = X in generated_terms_check
found_Y = Y in generated_terms_check
found_Z = Z in generated_terms_check
if found_X and found_Y and found_Z:
if min_A_sol == -1 or A_cand < min_A_sol or \
(A_cand == min_A_sol and B_cand < min_B_sol):
min_A_sol = A_cand
min_B_sol = B_cand
if min_A_sol != -1:
print(min_A_sol, min_B_sol)
else:
print("-1")
solve()