#991316 (PyPy3) No.2795 Perfect Number

提出ソース

結果

問題	No.2795 Perfect Number
ユーザー	chineristAC
提出日時	2024-06-28 21:39:54
言語	PyPy3 (7.3.15)
結果	AC
実行時間	52 ms / 2,000 ms
コード長	5,023 bytes
コンパイル時間	169 ms
コンパイル使用メモリ	82,204 KB
実行使用メモリ	63,580 KB
最終ジャッジ日時	2024-06-28 21:40:01
合計ジャッジ時間	2,651 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	44 ms 56,064 KB
testcase_01	AC	39 ms 56,192 KB
testcase_02	AC	40 ms 55,936 KB
testcase_03	AC	44 ms 56,064 KB
testcase_04	AC	40 ms 56,192 KB
testcase_05	AC	39 ms 56,448 KB
testcase_06	AC	40 ms 56,320 KB
testcase_07	AC	41 ms 56,192 KB
testcase_08	AC	38 ms 55,936 KB
testcase_09	AC	38 ms 56,320 KB
testcase_10	AC	38 ms 56,448 KB
testcase_11	AC	42 ms 56,064 KB
testcase_12	AC	41 ms 56,320 KB
testcase_13	AC	42 ms 55,936 KB
testcase_14	AC	43 ms 56,576 KB
testcase_15	AC	44 ms 56,448 KB
testcase_16	AC	42 ms 56,320 KB
testcase_17	AC	42 ms 56,448 KB
testcase_18	AC	42 ms 56,320 KB
testcase_19	AC	42 ms 56,064 KB
testcase_20	AC	43 ms 56,064 KB
testcase_21	AC	43 ms 56,320 KB
testcase_22	AC	52 ms 56,192 KB
testcase_23	AC	42 ms 56,320 KB
testcase_24	AC	42 ms 56,448 KB
testcase_25	AC	39 ms 56,448 KB
testcase_26	AC	39 ms 56,960 KB
testcase_27	AC	44 ms 62,848 KB
testcase_28	AC	41 ms 56,704 KB
testcase_29	AC	43 ms 56,320 KB
testcase_30	AC	41 ms 56,320 KB
testcase_31	AC	39 ms 56,320 KB
testcase_32	AC	38 ms 56,320 KB
testcase_33	AC	40 ms 56,320 KB
testcase_34	AC	40 ms 56,192 KB
testcase_35	AC	44 ms 63,580 KB
testcase_36	AC	39 ms 56,576 KB
testcase_37	AC	39 ms 56,832 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

class BinaryTrie:
    class node:
        def __init__(self):
            self.left = None
            self.right = None
            self.cnt = 0

    def __init__(self,n):
        self.root = self.node()
        self.n = n
        self.xor = 0
        self.set = set()
    
    def __len__(self):
        return self.root.cnt
    
    def __str__(self):
        res = []
        for val in self.set:
            res.append(val^self.xor)
        res.sort()
        res = ["["] + [str(val)+", " for val in res] + ["]"]
        return "".join(res)
    
    def append(self,x):
        x ^= self.xor
        if x in self.set:
            return 
        self.set.add(x)

        pos = self.root
        for i in range(self.n-1,-1,-1):
            pos.cnt += 1
            if x>>i & 1:
                if pos.right is None:
                    pos.right = self.node()
                pos = pos.right
            else:
                if pos.left is None:
                    pos.left = self.node()
                pos = pos.left
        pos.cnt = 1
    
    def all_prod(self,x):
        self.xor ^= x
    
    def mex(self):
        res = 0
        pos = self.root
        t = 1<<self.n
        for i in range(self.n-1,-1,-1):
            t >>= 1
            if self.xor>>i & 1:
                check = 0
                if pos.right:
                    check = pos.right.cnt
                if check==t:
                    res += t
                    if not pos.left:
                        return res
                    else:
                        pos = pos.left
                else:
                    if not pos.right:
                        return res
                    else:
                        pos = pos.right
            else:
                check = 0
                if pos.left:
                    check = pos.left.cnt
                if check==t:
                    res += t
                    if not pos.right:
                        return res
                    else:
                        pos = pos.right
                else:
                    if not pos.left:
                        return res
                    else:
                        pos = pos.left
        
        return res

import sys,random
from collections import deque

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

def isPrimeMR(n):
    if n==1:
        return 0
    d = n - 1
    d = d // (d & -d)
    L = [2, 3, 5, 7, 11, 13, 17]
    if n in L:
        return 1
    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):
    from math import gcd
    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 += 1 + i % 2
        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 sub_solve(S):
    """
    総和がSの単調列の数え上げ
    """
    dp = [0] * (S+1)
    dp[0] = 1
    for val in range(1,S+1):
        ndp = [0] * (S+1)
        for pre_S in range(S+1):
            for k in range((S-pre_S)//val+1):
                ndp[pre_S+k*val] += dp[pre_S]
        dp = ndp
    return dp[S]

def divisors(n):
    res = [1]
    prime = primeFactor(n)
    for p in prime:
        newres = []
        for d in res:
            for j in range(prime[p]+1):
                newres.append(d*p**j)
        res = newres
    res.sort()
    return res

def solve(N):
    pf = primeFactor(N)
    res = 1
    for p in pf:
        e = pf[p]
        res *= (1-p**(e+1))//(1-p)

    return res == 2*N

N = int(input())
print("Yes" if solve(N) else "No")

yukicoder

結果

テストケース

ソースコード