結果

問題 No.1218 Something Like a Theorem
ユーザー Kiri8128Kiri8128
提出日時 2020-09-04 21:41:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 75 ms / 2,000 ms
コード長 4,144 bytes
コンパイル時間 285 ms
コンパイル使用メモリ 87,016 KB
実行使用メモリ 71,848 KB
最終ジャッジ日時 2023-08-17 15:15:24
合計ジャッジ時間 2,674 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
71,848 KB
testcase_01 AC 71 ms
71,220 KB
testcase_02 AC 70 ms
71,064 KB
testcase_03 AC 69 ms
71,544 KB
testcase_04 AC 69 ms
71,440 KB
testcase_05 AC 70 ms
71,204 KB
testcase_06 AC 71 ms
71,432 KB
testcase_07 AC 71 ms
71,524 KB
testcase_08 AC 71 ms
71,488 KB
testcase_09 AC 74 ms
71,456 KB
testcase_10 AC 72 ms
71,540 KB
testcase_11 AC 75 ms
71,544 KB
testcase_12 AC 75 ms
71,820 KB
testcase_13 AC 73 ms
71,292 KB
testcase_14 AC 71 ms
71,116 KB
testcase_15 AC 71 ms
71,176 KB
testcase_16 AC 68 ms
71,588 KB
testcase_17 AC 70 ms
71,044 KB
権限があれば一括ダウンロードができます

ソースコード

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")
0