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();
}

AtCoderBeginnerContest280 D 問題 400 点 「Factorial and Multiple」

問題概要

制約

解法

お気持ち

AC コード

AtCoderBeginnerContest280 D 問題 400 点「Factorial and Multiple」