結果

問題 No.613 Solitude by the window
ユーザー lam6er
提出日時 2025-03-31 17:38:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 2,050 bytes
コンパイル時間 364 ms
コンパイル使用メモリ 82,128 KB
実行使用メモリ 54,176 KB
最終ジャッジ日時 2025-03-31 17:39:15
合計ジャッジ時間 1,957 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

def legendre_symbol(a, p):
    ls = pow(a, (p - 1) // 2, p)
    if ls == p - 1:
        return -1
    return ls

def tonelli_shanks(n, p):
    assert legendre_symbol(n, p) == 1, "n is not a square (mod p)"
    if p == 2:
        return 1
    if p % 4 == 3:
        x = pow(n, (p + 1) // 4, p)
        return x
    s = p - 1
    e = 0
    while s % 2 == 0:
        s //= 2
        e += 1
    z = 2
    while legendre_symbol(z, p) != -1:
        z += 1
    c = pow(z, s, p)
    x = pow(n, (s + 1) // 2, p)
    t = pow(n, s, p)
    m = e
    while t != 1:
        temp = t
        i = 0
        while temp != 1 and i < m:
            temp = pow(temp, 2, p)
            i += 1
        if i == m:
            return None
        b = pow(c, 1 << (m - i - 1), p)
        x = (x * b) % p
        t = (t * b * b) % p
        c = (b * b) % p
        m = i
    return x

def main():
    import sys
    N, M = map(int, sys.stdin.readline().split())
    if M == 2:
        print(0)
        return
    leg = legendre_symbol(3, M)
    exponent = pow(2, N, M * M - 1)
    if leg == 1:
        sqrt3 = tonelli_shanks(3, M)
        s = (2 + sqrt3) % M
        t = (2 - sqrt3) % M
        term1 = pow(s, exponent, M)
        term2 = pow(t, exponent, M)
        a_n = (term1 + term2) % M
    else:
        def multiply(a1, b1, a2, b2, mod):
            new_a = (a1 * a2 + 3 * b1 * b2) % mod
            new_b = (a1 * b2 + a2 * b1) % mod
            return new_a, new_b
        def pow_GF(a, b, exp, mod):
            res_a, res_b = 1, 0
            curr_a, curr_b = a, b
            while exp > 0:
                if exp % 2 == 1:
                    res_a, res_b = multiply(res_a, res_b, curr_a, curr_b, mod)
                curr_a, curr_b = multiply(curr_a, curr_b, curr_a, curr_b, mod)
                exp //= 2
            return res_a, res_b
        s_a, s_b = pow_GF(2, 1, exponent, M)
        t_a, t_b = pow_GF(2, M - 1, exponent, M)
        sum_a = (s_a + t_a) % M
        a_n = sum_a
    x_n = (a_n - 2) % M
    print(x_n)

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