AtCoderBeginnerContest280 D問題 400 点 「Factorial and Multiple」
AtCoderBeginnerContest280 D 問題 400 点 「Factorial and Multiple」
問題概要
制約
解法
$N!$が K の倍数になれば良いので,K に含まれる素因数とその個数が $1 \le i \le N$ に含まれていれば良い。 しかし,各素因数$p_i$について$q_i$個含む N を解析的に見つけるのは難しいため,二分探索を行う。 制約として$K \le 10^{12}$なので,$l = 0,\ r = 2^{60}$くらいにしてから,$p_i$の個数を調べる。 調べ方としては,$\sum_{q= 1} K / p^q$で調べることができる。これに気づけなかったのがつらい。 各素因数の中で最も大きい値が答えになる。素因数の出現回数を調べるときに,残りが 1 より大きい場合はそれも素数になることに注意。
お気持ち
AC コード
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(clippy::needless_range_loop)]
#![allow(clippy::comparison_chain)]
#![allow(clippy::nonminimal_bool)]
#![allow(clippy::neg_multiply)]
#![allow(dead_code)]
#![recursion_limit = "1024"]
use std::collections::{vec_deque, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::f64::consts::PI;
use std::mem::swap;
use std::ops::Index;
use itertools::{CombinationsWithReplacement, Itertools};
use num::{integer::Roots, traits::Pow, ToPrimitive};
use num_integer::{div_ceil, Integer};
use num_traits::{abs_sub, Float};
use permutohedron::Heap;
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::io::*;
use whiteread::parse_line;
//
fn is_ok(mid: usize, k: usize, v: usize) -> bool {
let mut mid = mid;
let mut cnt = 0;
while mid >= k {
cnt += mid / k;
mid /= k;
}
cnt >= v
}
fn solve() {
#[rustfmt::skip]
input! {
K:usize
}
let mut ans = 0;
let mut T = K;
let mut mp = HashMap::new();
for i in 2..(K as f64).sqrt() as usize + 1 {
if T % i == 0 {
let mut cnt = 0;
while T % i == 0 {
T /= i;
cnt += 1;
}
mp.insert(i, cnt);
}
}
if T > 1 {
mp.insert(T, 1);
}
for (&k, &v) in mp.iter() {
let mut ok = 1 << 60;
let mut ng = 0;
while ok - ng > 1 {
let mid = (ok + ng) / 2;
if is_ok(mid, k, v) {
ok = mid;
} else {
ng = mid;
}
// println!("ok = {ok}, ng = {ng}");
}
ans = ans.max(ok);
}
println!("{}", ans);
}
fn main() {
// input! {N:usize}
// for _ in 0..N {
// solve();
// }
solve();
}