結果

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

ソースコード

diff # 

def tonelli_shanks(n, p):
    assert pow(n, (p - 1) // 2, p) in (0, 1), "n is not a square (mod p)"
    if n == 0:
        return 0
    if p == 2:
        return n
    if p % 4 == 3:
        x = pow(n, (p + 1) // 4, p)
        return x
    Q = p - 1
    S = 0
    while Q % 2 == 0:
        Q //= 2
        S += 1
    for z in range(2, p):
        if pow(z, (p - 1) // 2, p) == p - 1:
            break
    c = pow(z, Q, p)
    x = pow(n, (Q + 1) // 2, p)
    t = pow(n, Q, p)
    m = S
    while t != 1:
        i, temp = 0, t
        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
    legendre = pow(3, (M - 1) // 2, M)
    if legendre == 1:
        r = tonelli_shanks(3, M)
        e = pow(2, N, M - 1)
        s = (2 + r) % M
        t_pow = pow((2 - r) % M, e, M)
        s_pow = pow(s, e, M)
        z = (s_pow + t_pow) % M
    else:
        def multiply(a1, b1, a2, b2, mod):
            a = (a1 * a2 + 3 * b1 * b2) % mod
            b = (a1 * b2 + a2 * b1) % mod
            return (a, b)
        def pow_ring(a, b, exponent, mod):
            res_a, res_b = 1, 0
            curr_a, curr_b = a, b
            while exponent > 0:
                if exponent % 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)
                exponent //= 2
            return (res_a, res_b)
        mod_ring = M * M - 1
        e = pow(2, N, mod_ring)
        sa, sb = pow_ring(2, 1, e, M)
        ta, tb = pow_ring(2, M - 1, e, M)
        z = (sa + ta) % M
    x = (z - 2) % M
    print(x)

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