結果
問題 | No.1396 Giri |
ユーザー |
![]() |
提出日時 | 2021-02-14 21:33:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 98 ms / 2,000 ms |
コード長 | 770 bytes |
コンパイル時間 | 205 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 80,768 KB |
最終ジャッジ日時 | 2024-07-22 08:54:34 |
合計ジャッジ時間 | 2,820 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
def Eratosthenes(N): #N以下の素数のリストを返す #iが素数のときis_prime_list[i]=1,それ以外は0 N+=1 is_prime_list = [True]*N # is_prime_list[0], is_prime_list[1] = False, False #リストが必要なときはこの2行を有効化 # for j in range(4,N,2): is_prime_list[j] = False m = int(N**0.5)+1 for i in range(3,m,2): if is_prime_list[i]: is_prime_list[i*i::2*i]=[False]*((N-i*i-1)//(2*i)+1) return [2] + [i for i in range(3,N,2) if is_prime_list[i]] # return is_prime_list n = int(input()) primes = Eratosthenes(n) primes.pop() ans = 1 MOD = 998244353 for p in primes: c = 0 nn = n//p while nn: c += 1 nn //= p ans *= pow(p,c,MOD) ans %= MOD print(ans)