結果

問題 No.950 行列累乗
ユーザー lam6er
提出日時 2025-04-16 16:46:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,273 bytes
コンパイル時間 429 ms
コンパイル使用メモリ 82,132 KB
実行使用メモリ 83,036 KB
最終ジャッジ日時 2025-04-16 16:49:45
合計ジャッジ時間 5,743 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def matrix_mult(a, b, mod):
    res = [[0]*2 for _ in range(2)]
    res[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % mod
    res[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % mod
    res[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % mod
    res[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % mod
    return res

def matrix_pow(mat, power, mod):
    result = [[1, 0], [0, 1]]  # Identity matrix
    while power > 0:
        if power % 2 == 1:
            result = matrix_mult(result, mat, mod)
        mat = matrix_mult(mat, mat, mod)
        power = power // 2
    return result

def baby_step_giant_step(g, h, p):
    if h == 1:
        return 0
    if g == 0:
        return -1
    m = int(math.isqrt(p)) + 1
    table = dict()
    current = 1
    for j in range(m):
        if current not in table:
            table[current] = j
        current = (current * g) % p
    gm = pow(g, m, p)
    gm_inv = pow(gm, p-2, p)
    current = h
    for i in range(m):
        if current in table:
            return i * m + table[current]
        current = (current * gm_inv) % p
    return -1

def factorize(n):
    factors = {}
    while n % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        n = n // 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors[i] = factors.get(i, 0) + 1
            n = n // i
        i += 2
    if n > 1:
        factors[n] = 1
    return sorted(factors.items())

def find_order(a, p):
    if a == 0:
        return -1
    if a == 1:
        return 1
    factors = factorize(p - 1)
    order = p - 1
    for (prime, exp) in factors:
        for _ in range(exp):
            if pow(a, order // prime, p) == 1:
                order = order // prime
            else:
                break
    return order

def main():
    p = int(input())
    A = [list(map(int, input().split())) for _ in range(2)]
    B = [list(map(int, input().split())) for _ in range(2)]
    mod = p

    def mat_eq(a, b):
        return (a[0][0] % mod == b[0][0] % mod and
                a[0][1] % mod == b[0][1] % mod and
                a[1][0] % mod == b[1][0] % mod and
                a[1][1] % mod == b[1][1] % mod)

    det_A = (A[0][0] * A[1][1] - A[0][1] * A[1][0]) % mod
    det_B = (B[0][0] * B[1][1] - B[0][1] * B[1][0]) % mod

    if det_A == 0:
        if det_B != 0:
            print(-1)
            return
        else:
            is_A_zero = all(cell % mod == 0 for row in A for cell in row)
            is_B_zero = all(cell % mod == 0 for row in B for cell in row)
            if is_A_zero:
                if is_B_zero:
                    print(1)
                else:
                    print(-1)
                return
            else:
                if is_B_zero:
                    current = [row.copy() for row in A]
                    k = 1
                    for _ in range(100):
                        is_zero = all(cell % mod == 0 for row in current for cell in row)
                        if is_zero:
                            print(k)
                            return
                        current = matrix_mult(current, A, mod)
                        k += 1
                    print(-1)
                    return
                else:
                    current = [row.copy() for row in A]
                    k = 1
                    for _ in range(100):
                        if mat_eq(current, B):
                            print(k)
                            return
                        current = matrix_mult(current, A, mod)
                        k += 1
                    print(-1)
                    return
    else:
        g = det_A % mod
        h = det_B % mod
        x0 = baby_step_giant_step(g, h, mod)
        if x0 == -1:
            print(-1)
            return
        d = find_order(g, mod)
        if d == -1:
            print(-1)
            return
        if x0 <= 0:
            k = (1 - x0 + d - 1) // d
            n = x0 + k * d
        else:
            n = x0
        for _ in range(100):
            if n > 0:
                An = matrix_pow(A, n, mod)
                if mat_eq(An, B):
                    print(n)
                    return
            n += d
        print(-1)

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