結果

問題 No.195 フィボナッチ数列の理解(2)
ユーザー rpy3cpprpy3cpp
提出日時 2016-02-14 16:04:47
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 33 ms / 5,000 ms
コード長 3,342 bytes
コンパイル時間 94 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 10,432 KB
最終ジャッジ日時 2023-10-22 05:14:41
合計ジャッジ時間 1,723 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
10,432 KB
testcase_01 AC 29 ms
10,432 KB
testcase_02 AC 32 ms
10,432 KB
testcase_03 AC 31 ms
10,432 KB
testcase_04 AC 32 ms
10,432 KB
testcase_05 AC 30 ms
10,432 KB
testcase_06 AC 30 ms
10,432 KB
testcase_07 AC 30 ms
10,432 KB
testcase_08 AC 30 ms
10,432 KB
testcase_09 AC 30 ms
10,432 KB
testcase_10 AC 33 ms
10,432 KB
testcase_11 AC 32 ms
10,432 KB
testcase_12 AC 32 ms
10,432 KB
testcase_13 AC 33 ms
10,432 KB
testcase_14 AC 32 ms
10,432 KB
testcase_15 AC 32 ms
10,432 KB
testcase_16 AC 31 ms
10,432 KB
testcase_17 AC 31 ms
10,432 KB
testcase_18 AC 31 ms
10,432 KB
testcase_19 AC 31 ms
10,432 KB
testcase_20 AC 32 ms
10,432 KB
testcase_21 AC 33 ms
10,432 KB
testcase_22 AC 32 ms
10,432 KB
testcase_23 AC 32 ms
10,432 KB
testcase_24 AC 32 ms
10,432 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def gcd_ext(m: int, n: int) -> (int, int, int):
    '''拡張ユークリッドの互除法
    mx + ny = gcd(m, n)
    となる、gcd(m, n), x, y を返す。
    '''
    x, y, u, v = 1, 0, 0, 1
    while n:
        k, m = divmod(m, n)
        m, n = n, m
        x, y, u, v = u, v, x - u * k, y - v * k
    return m, x, y


def fibs(n):
    a = 1
    b = 0
    result = [a]
    for i in range(n - 1):
        a, b = b, a + b
        result.append(a)
    return result

def solve(X, Y, Z):
    xyz = set([X, Y, Z])
    length = len(xyz)
    if length == 3:
        return solve3(X, Y, Z)
    elif length == 2:
        return solve2(*xyz)
    else:
        return solve1(X)

def solve1(X):
    ''' X = 15 のときに上手くいかない。
    '''
    if X == 1:
        return 1, 1
    N = 50
    fib = fibs(N)
    record = (float('inf'), float('inf'))
    for fi, gi in zip(fib[2:], fib[3:]):
        # fi * A + gi * B = X となる A, B で辞書順最小を求めたい。
        gcdfg, a, b = gcd_ext(fi, gi)
        q, r = divmod(X, gcdfg)
        if r:
            continue
        A, B = findAB1(a * q, b * q, gi*gcdfg, fi*gcdfg)
        if A > 0 and (A, B) < record:
            record = (A, B)
    if record != (float('inf'), float('inf')):
        return record
    else:
        return (-1, )

def findAB1(a, b, da, db):
    '''
    A = a + t * da
    B = b - t * db
    B > 0
    A > 0
    のとき、A を最小とする t を求め、そのときの A, B を返す。
    条件を満たす A, B が無いときは、0, 0 を返す。
    a + t * da > 0
    t > -a/da
    b - t * db > 0
    t < b/db
    b/db > t > -a/da
    '''
    if a > 0:
        if a % da:
            t = - (a // da)
        else:
            t = 1 - (a // da)
    else:
        t = 1 + (-a)//da
    A = a + t * da
    B = b - t * db
    if A > 0 and B > 0:
        return A, B
    else:
        return 0, 0


def solve2(X, Y):
    return solve3(X, Y, Y)


def solve3(X, Y, Z):
    N = 50
    fib = fibs(N)
    record = (float('inf'), float('inf'))
    for i in range(N - 1):
        for j in range(N - 1):
            if i == j:
                continue
            A, B = findAB3(i, j, X, Y, fib)
            if A and (A, B) < record and is_valid(A, B, fib, Z):
                record = (A, B)
    if record != (float('inf'), float('inf')):
        return record
    else:
        return (-1, )

def findAB3(i, j, X, Y, fib):
    '''
    fi * A + gi * B = X
    fj * A + gj * B = Y
    となる 正整数　A, B を求める。
    fi*fj * A + gi*fj * B = X*fj
    fi*fj * A + gj*fi * B = Y*fi
    (gi*fj - gj*fi) * B = X*fj - Y*fi
    B = -(fj*X - fi*Y)/(fi*gj - fj*gi)
    A = (gj*X - gi*Y)/(fi*gj - fj*gi)
    '''
    fi = fib[i]
    gi = fib[i + 1]
    fj = fib[j]
    gj = fib[j + 1]
    det = fi * gj - fj * gi
    if det == 0:
        return 0, 0
    A, ra = divmod(gj * X - gi * Y, det)
    B, rb = divmod(-(fj * X - fi * Y), det)
    if A <= 0 or B <= 0 or ra or rb:
        return 0, 0
    return A, B

def is_valid(A, B, fib, Z):
    '''
    fib[i] * A + fib[i + 1] * B = Z
    となる i が存在するか調べる。
    '''
    for fi, gi in zip(fib, fib[1:]):
        if fi * A + gi * B == Z:
            return True
    return False

if __name__ == '__main__':
    X, Y, Z = map(int, input().split())
    print(*solve(X, Y, Z))
0