結果
問題 |
No.1529 Constant Lcm
|
ユーザー |
![]() |
提出日時 | 2025-03-26 15:53:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 85 ms / 3,000 ms |
コード長 | 1,830 bytes |
コンパイル時間 | 254 ms |
コンパイル使用メモリ | 82,096 KB |
実行使用メモリ | 75,084 KB |
最終ジャッジ日時 | 2025-03-26 15:54:08 |
合計ジャッジ時間 | 2,770 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
ソースコード
import math MOD = 998244353 def sieve(n): if n < 2: return [] is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(math.sqrt(n)) + 1): if is_prime[i]: for j in range(i * i, n + 1, i): is_prime[j] = False primes = [i for i, val in enumerate(is_prime) if val] return primes def factorize(n): factors = {} i = 2 while i * i <= n: while n % i == 0: factors[i] = factors.get(i, 0) + 1 n //= i i += 1 if n > 1: factors[n] = 1 return factors def main(): N = int(input()) if N == 1: print(1) return factors = factorize(N) primes = sieve(N - 1) if N - 1 >= 2 else [] ans = 1 processed_primes = set() for p in primes: if p in factors: k = factors[p] m = N // (p ** k) if m == 1: max_e = 2 * (k - 1) else: s_max = 0 current = 1 while current * p <= m - 1: current *= p s_max += 1 max_e = 2 * k + s_max ans = ans * pow(p, max_e, MOD) % MOD processed_primes.add(p) else: a_max = 0 current = 1 while current * p <= N - 1: current *= p a_max += 1 if a_max >= 1: ans = ans * pow(p, a_max, MOD) % MOD for p in factors: if p > N - 1 and p not in processed_primes: k = factors[p] m = N // (p ** k) if m == 1: max_e = 2 * (k - 1) ans = ans * pow(p, max_e, MOD) % MOD print(ans % MOD) if __name__ == "__main__": main()