結果
問題 |
No.3296 81-like number
|
ユーザー |
|
提出日時 | 2025-10-05 13:36:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 1,703 bytes |
コンパイル時間 | 252 ms |
コンパイル使用メモリ | 82,120 KB |
実行使用メモリ | 74,092 KB |
最終ジャッジ日時 | 2025-10-05 13:38:24 |
合計ジャッジ時間 | 2,334 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
def sieves(nn: int): is_prime = [True] * nn least_p = [-1] * nn is_prime[0] = is_prime[1] = False least_p[1] = 1 mobius = [1] * nn mobius[0] = 0 for p in range(2, nn): if not is_prime[p]: continue least_p[p] = p mobius[p] = -1 for q in range(p * 2, nn, p): is_prime[q] = False if least_p[q] == -1: least_p[q] = p if q % (p * p) == 0: mobius[q] = 0 else: mobius[q] *= -1 primes = [p for p in range(2, nn) if is_prime[p]] return is_prime, least_p, primes, mobius def prime_factorize(n: int): ans = {} while n > 1: p = least_p[n] e = 0 while n % p == 0: n //= p e += 1 ans[p] = e return ans def get_divisors(n: int): """正の約数列挙 Args: n (int): 約数を求める数 (>= 1) Returns: list[int]: `n`の正の約数 Notes: - `n`の約数の個数をσ(n)として - 計算量 Θ( σ(n) * log(σ(n)) ) - n <= 10^7 で σ(n) <= σ(8648640) = 448 - n <= 10^9 で σ(n) <= σ(735134400) = 1344 - n <= 10^18 で σ(n) <= σ(897612484786617600) = 103680 """ pe = prime_factorize(n) ans = [1] for p, e in pe.items(): exps = [p ** ei for ei in range(1, e + 1)] ans.extend([d * f for d in ans for f in exps]) ans.sort() return ans is_prime, least_p, primes, mobius = sieves(10**5 * 2 + 1) n = int(input()) ans = 0 for p in primes: pe = p * p if pe > n: break while pe <= n: ans += pe pe *= p print(ans)