結果
問題 | No.1396 Giri |
ユーザー |
![]() |
提出日時 | 2025-03-26 15:57:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,615 ms / 2,000 ms |
コード長 | 3,200 bytes |
コンパイル時間 | 234 ms |
コンパイル使用メモリ | 82,880 KB |
実行使用メモリ | 272,572 KB |
最終ジャッジ日時 | 2025-03-26 15:59:03 |
合計ジャッジ時間 | 15,300 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
import sys import math from collections import defaultdict MOD = 998244353 def main(): N = int(sys.stdin.readline()) if N == 1: print(1) return # Sieve of Eratosthenes to find smallest prime factors lpf = list(range(N + 1)) for i in range(2, int(math.isqrt(N)) + 1): if lpf[i] == i: for j in range(i*i, N+1, i): if lpf[j] == j: lpf[j] = i # Factorize each number and collect prime exponents prime_exp = defaultdict(list) max_exp = {} next_max = {} count_max = {} for i in range(2, N+1): x = i factors = defaultdict(int) while x > 1: p = lpf[x] factors[p] += 1 x //= p for p, e in factors.items(): prime_exp[p].append(e) # Determine max_exp, next_max, count_max for each prime for p in prime_exp: exp_list = prime_exp[p] unique_exps = sorted(list(set(exp_list)), reverse=True) max_e = unique_exps[0] max_exp[p] = max_e count_max[p] = exp_list.count(max_e) if len(unique_exps) >= 2: next_max[p] = unique_exps[1] else: next_max[p] = 0 # Compute log_L for the overall LCM log_L = 0.0 for p in max_exp: log_L += max_exp[p] * math.log(p) # Find the i with the minimum log after removal min_log = float('inf') best_i = 1 # default to i=1 for i in range(1, N+1): current_log = log_L if i != 1: # Factorize i x = i factors = defaultdict(int) while x > 1: p = lpf[x] factors[p] += 1 x //= p # Check each prime factor of i for p, e in factors.items(): if p not in max_exp: continue if e == max_exp[p]: if count_max[p] == 1: delta_e = max_exp[p] - next_max.get(p, 0) current_log -= delta_e * math.log(p) # Update minimum if current_log < min_log: min_log = current_log best_i = i # Compute the LCM mod MOD for the best_i # First compute the overall LCM mod MOD lcm_mod = 1 for p in max_exp: lcm_mod = lcm_mod * pow(p, max_exp[p], MOD) % MOD if best_i == 1: print(lcm_mod % MOD) return # Factorize best_i x = best_i factors = defaultdict(int) while x > 1: p = lpf[x] factors[p] += 1 x //= p # Adjust the LCM mod MOD by removing best_i's contribution res = lcm_mod for p in factors: if p not in max_exp: continue e_i = factors[p] if e_i == max_exp[p] and count_max[p] == 1: # Remove p^max_exp and multiply p^next_max exponent_remove = max_exp[p] exponent_add = next_max.get(p, 0) inv = pow(p, exponent_remove, MOD) inv = pow(inv, MOD-2, MOD) res = res * inv % MOD res = res * pow(p, exponent_add, MOD) % MOD print(res % MOD) if __name__ == "__main__": main()