結果
問題 |
No.613 Solitude by the window
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()