https://atcoder.jp/contests/abc280/tasks/abc280_d
素因数分解すれば、あとは素数ごとに計算すればよいですね。
素数ごとに条件を満たす最小の倍数を求める部分はもっと効率のいい方法があると思いますが、素因数分解に比べれば十分に速いですね。
// Factorial and Multiple #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn div_pow(n: i64, d: i64) -> (u32, i64) { if n % d == 0 { let (e, m) = div_pow(n / d, d); (e + 1, m) } else { (0, n) } } type Factors = Vec<(i64, u32)>; fn factorize(n: i64, p0: i64) -> Factors { if n == 1 { return vec![] } for p in p0.. { if p * p > n { break } if n % p == 0 { let (e, m) = div_pow(n, p); let factors = factorize(m, p + 1); let mut new_factors = vec![(p, e)]; new_factors.extend(&factors); return new_factors } } vec![(n, 1)] } fn num_primes(n: i64, p: i64) -> u32 { let mut num = 0; let mut q = p; while q <= n { num += n / q; q *= p } num as u32 } fn min_num((p, e): (i64, u32)) -> i64 { for n in (p..).step_by(p as usize) { if num_primes(n, p) >= e { return n } } p } fn f(K: i64) -> i64 { let fs = factorize(K, 2); fs.into_iter().map(|f| min_num(f)).max().unwrap() } fn main() { let K: i64 = read(); println!("{}", f(K)) }