結果

問題 No.195 フィボナッチ数列の理解(2)
コンテスト
ユーザー titia
提出日時 2026-03-12 04:09:46
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 60 ms / 5,000 ms
コード長 3,005 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 750 ms
コンパイル使用メモリ 85,212 KB
実行使用メモリ 81,400 KB
最終ジャッジ日時 2026-03-12 04:09:55
合計ジャッジ時間 2,997 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# 解説を読んだ。なるほど。

import sys
input = sys.stdin.readline

# 行列の計算（numpyを使えないとき,modを使用）
def prod(A,B,k,l,m):# A:k*l,B:l*m
    C=[[None for i in range(m)] for j in range(k)]

    for i in range(k):
        for j in range(m):
            ANS=0
            for pl in range(l):
                ANS=(ANS+A[i][pl]*B[pl][j])

            C[i][j]=ANS

    return C

def plus(A,B,k,l):# a,B:k*l
    C=[[None for i in range(l)] for j in range(k)]

    for i in range(k):
        for j in range(l):
            C[i][j]=(A[i][j]+B[i][j])

    return C

A=list(map(int,input().split()))

A=sorted(set(A))

F=[0,1]

for i in range(50):
    F.append(F[-1]+F[-2])

G=[1,0]

for i in range(50):
    G.append(G[-1]+G[-2])

if len(A)>=2:
    x=A[0]
    y=A[1]

    if len(A)==3:
        z=A[2]
    else:
        z=A[0]

    MIN=(1<<60,1<<60)

    for i in range(50):
        for j in range(50):
            if i==j:
                continue
            X=[[F[i],G[i]],[F[j],G[j]]]

            a=X[0][0]
            b=X[0][1]
            c=X[1][0]
            d=X[1][1]

            if a*d-b*c==0:
                continue

            k=1/(a*d-b*c)
            
            
            INV=[[d*k,-b*k],[-c*k,a*k]]

            C=prod(INV,[[x],[y]],2,2,1)

            #print(i,j,X,INV,C)



            D=(C[0][0],C[1][0])

            #print(D)

            if D[0]>0 and D[1]>0 and abs(D[0]-round(D[0]))<0.00000001 and abs(D[1]-round(D[1]))<0.00000001:
                D=(round(D[1]),round(D[0]))
                #print(D,i,j,X,INV)
                FX=[D[0],D[1]]



                for k in range(50):
                    FX.append(FX[-1]+FX[-2])

                #print(FX)

                if z in FX:
                    MIN=min(MIN,D)

    if MIN[0]<10**12:
        print(*MIN)
    else:
        print(-1)

else:
    x=1
    y=A[0]

    if len(A)==3:
        z=A[2]
    else:
        z=1

    MIN=(1<<60,1<<60)

    for i in range(50):
        for j in range(50):
            if i==j:
                continue
            X=[[F[i],G[i]],[F[j],G[j]]]

            a=X[0][0]
            b=X[0][1]
            c=X[1][0]
            d=X[1][1]

            if a*d-b*c==0:
                continue

            k=1/(a*d-b*c)
            
            
            INV=[[d*k,-b*k],[-c*k,a*k]]

            C=prod(INV,[[x],[y]],2,2,1)

            #print(i,j,X,INV,C)



            D=(C[0][0],C[1][0])

            #print(D)

            if D[0]>0 and D[1]>0 and abs(D[0]-round(D[0]))<0.00000001 and abs(D[1]-round(D[1]))<0.00000001:
                D=(round(D[1]),round(D[0]))
                #print(D,i,j,X,INV)
                FX=[D[0],D[1]]



                for k in range(50):
                    FX.append(FX[-1]+FX[-2])

                #print(FX)

                if z in FX:
                    MIN=min(MIN,D)

    if MIN[0]<10**12:
        print(*MIN)
    else:
        print(-1)
0