結果
問題 | No.1218 Something Like a Theorem |
ユーザー |
![]() |
提出日時 | 2020-09-04 21:41:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 4,144 bytes |
コンパイル時間 | 258 ms |
コンパイル使用メモリ | 81,904 KB |
実行使用メモリ | 55,232 KB |
最終ジャッジ日時 | 2024-11-26 12:16:33 |
合計ジャッジ時間 | 1,725 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 16 |
ソースコード
from math import atan2def gcd(a, b):while b: a, b = b, a % breturn adef isPrimeMR(n):d = n - 1d = d // (d & -d)L = [2, 7, 61] if n < 1<<32 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]for a in L:t = dy = pow(a, t, n)if y == 1: continuewhile y != n - 1:y = y * y % nif y == 1 or t == n - 1: return 0t <<= 1return 1def findFactorRho(n):m = 1 << n.bit_length() // 8for c in range(1, 99):f = lambda x: (x * x + c) % ny, r, q, g = 2, 1, 1, 1while g == 1:x = yfor i in range(r):y = f(y)k = 0while k < r and g == 1:ys = yfor i in range(min(m, r - k)):y = f(y)q = q * abs(x - y) % ng = gcd(q, n)k += mr <<= 1if g == n:g = 1while g == 1:ys = f(ys)g = gcd(abs(x - ys), n)if g < n:if isPrimeMR(g): return gelif isPrimeMR(n // g): return n // greturn findFactorRho(g)def primeFactor(n):i = 2ret = {}rhoFlg = 0while i * i <= n:k = 0while n % i == 0:n //= ik += 1if k: ret[i] = ki += i % 2 + (3 if i % 3 == 1 else 1)if i == 101 and n >= 2 ** 20:while n > 1:if isPrimeMR(n):ret[n], n = 1, 1else:rhoFlg = 1j = findFactorRho(n)k = 0while n % j == 0:n //= jk += 1ret[j] = kif n > 1: ret[n] = 1if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}return retdef divisors(N):pf = primeFactor(N)ret = [1]for p in pf:ret_prev = retret = []for i in range(pf[p]+1):for r in ret_prev:ret.append(r * (p ** i))return sorted(ret)def factor_prime(p): # find a, b such that a ** 2 + b ** 2 == p, given a prime p with p = 4n+1 for some n# assert isPrime(p) and p % 4 == 1for i in range(p):if pow(i, (p-1) // 2, p) == p - 1:a, b = pow(i, (p-1) // 4, p), 1breakk = (a ** 2 + b ** 2) // pwhile k > 1:kk = k // 2na, nb = (a + kk) % k - kk, (b + kk) % k - kka, b = (a * na + b * nb) // k, (a * nb - b * na) // kk = (a ** 2 + b ** 2) // preturn (abs(a), abs(b))def factor(n): # find all the pairs of (a, b) such that a ** 2 + b ** 2 == ndef mult(a, b):return (a[0] * b[0] - a[1] * b[1], a[0] * b[1] + a[1] * b[0])def mult_all(L1, L2):nL = []for l1 in L1:for l2 in L2:nL.append(mult(l1, l2))return nLdef conj(x):return (x[0], -x[1])if n == 0: return [(0, 0)]pf = primeFactor(n)L = [(1, 0)]for p in pf:if p == 2:for _ in range(pf[p]):L = mult_all(L, [(1, 1)])continueif p % 4 == 3:if pf[p] % 2:return []L = mult_all(L, [(p ** (pf[p] // 2), 0)])continuex = (1, 0)cL = [x]t = factor_prime(p)for _ in range(pf[p]):x = mult(x, t)cL.append(x)y = (1, 0)t = conj(t)for i in range(pf[p] + 1):cL[-i-1] = mult(cL[-i-1], y)y = mult(y, t)L = mult_all(L, cL)return sorted([mult(l, x) for l in L for x in ((1, 0), (0, 1), (-1, 0), (0, -1))], key = lambda x: -atan2(x[1], -x[0]))n, z = map(int, input().split())if n == 1:print("Yes" if z >= 2 else "No")elif n > 2:print("No")else:for a, b in factor(z ** n):if a > 0 and b > 0:print("Yes")breakelse:print("No")