結果
問題 | No.2902 ZERO!! |
ユーザー |
![]() |
提出日時 | 2024-09-27 20:23:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 627 ms / 2,000 ms |
コード長 | 1,590 bytes |
コンパイル時間 | 279 ms |
コンパイル使用メモリ | 82,196 KB |
実行使用メモリ | 113,480 KB |
最終ジャッジ日時 | 2024-09-27 20:23:48 |
合計ジャッジ時間 | 11,650 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
class Eratosthenes:def __init__(self, n):self.isPrime = [True]*(n+1)self.minfactor = [-1]*(n+1)self.isPrime[0], self.isPrime[1] = False, Falseself.minfactor[1] = 1for i in range(2, n+1):if self.isPrime[i]:self.minfactor[i] = ifor j in range(i*2, n+1, i):self.isPrime[j] = Falseif self.minfactor[j] == -1:self.minfactor[j] = idef factorize(self, n):factor = []while n > 1:p = self.minfactor[n]cnt = 0while self.minfactor[n] == p:n //= pcnt += 1factor.append((p, cnt))return factordef divisor(self, n):ans = [1]pf = self.factorize(n)for p, c in pf:L = len(ans)for i in range(L):v = 1for _ in range(c):v *= pans.append(ans[i]*v)return sorted(ans)N = int(input())E = Eratosthenes(N)D = dict()for i in range(2, N+1):for n, c in E.factorize(i):if n in D:D[n] += celse:D[n] = cD = sorted([(n, c) for n, c in D.items()], key=lambda x:x[1], reverse=True)MOD = 998244353ans = 0for i in range(1, 1000000):cnt = 1for n, c in D:if c >= i:cnt *= c//i+1cnt %= MODelse:breakcnt -= 1cnt %= MODans += cntans %= MODprint(ans)