結果

問題 No.1218 Something Like a Theorem
ユーザー Kiri8128
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from math import atan2
def gcd(a, b):
while b: a, b = b, a % b
return a
def isPrimeMR(n):
d = n - 1
d = 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 = d
y = pow(a, t, n)
if y == 1: continue
while y != n - 1:
y = y * y % n
if y == 1 or t == n - 1: return 0
t <<= 1
return 1
def findFactorRho(n):
m = 1 << n.bit_length() // 8
for c in range(1, 99):
f = lambda x: (x * x + c) % n
y, r, q, g = 2, 1, 1, 1
while g == 1:
x = y
for i in range(r):
y = f(y)
k = 0
while k < r and g == 1:
ys = y
for i in range(min(m, r - k)):
y = f(y)
q = q * abs(x - y) % n
g = gcd(q, n)
k += m
r <<= 1
if g == n:
g = 1
while g == 1:
ys = f(ys)
g = gcd(abs(x - ys), n)
if g < n:
if isPrimeMR(g): return g
elif isPrimeMR(n // g): return n // g
return findFactorRho(g)
def primeFactor(n):
i = 2
ret = {}
rhoFlg = 0
while i * i <= n:
k = 0
while n % i == 0:
n //= i
k += 1
if k: ret[i] = k
i += 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, 1
else:
rhoFlg = 1
j = findFactorRho(n)
k = 0
while n % j == 0:
n //= j
k += 1
ret[j] = k
if n > 1: ret[n] = 1
if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
return ret
def divisors(N):
pf = primeFactor(N)
ret = [1]
for p in pf:
ret_prev = ret
ret = []
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 == 1
for i in range(p):
if pow(i, (p-1) // 2, p) == p - 1:
a, b = pow(i, (p-1) // 4, p), 1
break
k = (a ** 2 + b ** 2) // p
while k > 1:
kk = k // 2
na, nb = (a + kk) % k - kk, (b + kk) % k - kk
a, b = (a * na + b * nb) // k, (a * nb - b * na) // k
k = (a ** 2 + b ** 2) // p
return (abs(a), abs(b))
def factor(n): # find all the pairs of (a, b) such that a ** 2 + b ** 2 == n
def 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 nL
def 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)])
continue
if p % 4 == 3:
if pf[p] % 2:
return []
L = mult_all(L, [(p ** (pf[p] // 2), 0)])
continue
x = (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")
break
else:
print("No")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0