提出 #60552451

---

ソースコード 拡げる

use std::ops::RangeFrom;

use nekolib::{algo::Bisect, math::LinearSieve};
use proconio::input;

fn main() {
    input! {
        n: usize,
    }

    let n_4 = (1_usize..).bisect(|i| i.pow(4) <= n) - 1;
    let ls = LinearSieve::new(n_4);

    let res8 = ls.primes().map_while(|x| x.checked_pow(8)).take_while(|&x| x <= n).count();

    let n_2 = (1_usize..).bisect(|i| i.pow(2) <= n) - 1;
    let pi = lucy_2_3_log3(n_2);

    let res2: usize = ls
        .primes()
        .zip(1..)
        .map(|(p, i)| {
            let p = n_2 / p;
            (if p * p <= n_2 { pi[pi.len() - p] } else { pi[n_2 / p] }) - i
        })
        .sum();
    println!("{}", res8 + res2);
}

fn lucy_2_3_log3(n: usize) -> Vec<usize> {
    let n_2 = (1_usize..).bisect(|i| i.pow(2) <= n) - 1;
    let n_6 = (1_usize..).bisect(|i| i.pow(6) <= n) - 1;

    let lg = 1.max(n.next_power_of_two().trailing_zeros() as usize);
    let nlg_3 = (1_usize..).bisect(|i| i.pow(3) <= n * lg) - 1;
    let n_lg2_3 = (1_usize..).bisect(|i| i.pow(3) * lg.pow(2) <= n) - 1;

    let mut h = vec![0];
    h.extend((1..=n_2).map(|i| n / i));
    h.extend((1..n / n_2).rev());
    let ns = h.clone();
    for hi in &mut h[1..] {
        *hi -= 1;
    }

    let primes: Vec<_> = LinearSieve::new(n_2).primes().collect();

    let mut pi = 0;
    while pi < primes.len() && primes[pi] <= n_6 {
        let p = primes[pi];
        let pp = p * p;
        for (&n_i, i) in ns[1..].iter().take_while(|&&n_i| n_i >= pp).zip(1..) {
            let ip = i * p;
            h[i] -= h[if ip <= n_2 { ip } else { ns.len() - n_i / p }] - pi;
        }
        pi += 1;
    }

    let thresh = if nlg_3 <= n_2 { nlg_3 } else { ns.len() - n / nlg_3 };
    let mut rsq = FenwickTree::new(ns.len() - thresh);
    while pi < primes.len() && primes[pi] <= n_lg2_3 {
        let p = primes[pi];
        let pp = p * p;
        for (&n_i, i) in ns[1..].iter().take_while(|&&n_i| n_i >= pp).zip(1..=thresh) {
            let ip = i * p;
            let index = if ip <= n_2 { ip } else { ns.len() - n_i / p };

            let mut sum: usize = h[index];
            if index > thresh {
                sum -= rsq.sum(index - thresh..);
            }
            h[i] -= sum - pi;
        }

        let mut st = vec![(p, pi)];
        while let Some((cur, i)) = st.pop() {
            for (cur, j) in primes[i..].iter().map(|&p_j| cur * p_j).take_while(|&cur| cur < n / nlg_3).zip(i..) {
                let index = if cur <= n_2 { ns.len() - cur } else { n / cur };
                if index > thresh {
                    rsq.add(index - thresh, 1);
                }
                st.push((cur, j));
            }
        }

        pi += 1;
    }

    let rsq = rsq.into_suffix_sum();
    for i in 0..rsq.len() {
        h[i + thresh] -= rsq[i];
    }

    while pi < primes.len() && primes[pi] <= n_2 {
        let p = primes[pi];
        let pp = p * p;
        for (&n_i, i) in ns[1..].iter().take_while(|&&n_i| n_i >= pp).zip(1..) {
            let ip = i * p;
            h[i] -= h[if ip <= n_2 { ip } else { ns.len() - n_i / p }] - pi;
        }
        pi += 1;
    }

    h
}

struct FenwickTree(Vec<usize>);

impl FenwickTree {
    pub fn new(n: usize) -> Self { Self(vec![0; n]) }
    pub fn sum(&self, rf: RangeFrom<usize>) -> usize {
        let mut i = rf.start;
        let mut res = 0;
        while i < self.0.len() {
            res += self.0[i];
            i += i & i.wrapping_neg();
        }
        res
    }
    pub fn add(&mut self, mut i: usize, d: usize) {
        while i > 0 {
            self.0[i] += d;
            i -= i & i.wrapping_neg();
        }
    }
    pub fn into_suffix_sum(self) -> Vec<usize> {
        let mut res = self.0;
        for i in (1..res.len()).rev() {
            let j = i + (i & i.wrapping_neg());
            if j < res.len() {
                res[i] += res[j];
            }
        }
        res
    }
}

/// This module is bundled automatically.
/// See <https://rsk0315.github.io/nekolib/nekolib_doc/index.html> for documentation.
/// Commit: 469616556e6ab4c8e8e98302edd818646f996365-dirty
#[allow(unused)]
#[allow(private_interfaces)]
pub mod nekolib {
    pub mod algo {
        pub mod bisect {
            use std::ops::{Range, RangeFrom, RangeTo};
            pub trait Bisect {
                type Input;
                type Output;
                fn bisect(&self, pred: impl Fn(&Self::Input) -> bool) -> Self::Output;
            }
            macro_rules! impl_bisect_uint {
                            ( $($ty:ty)* ) => { $(
                                impl Bisect for Range<$ty> {
                                    type Input = $ty;
                                    type Output = $ty;
                                    fn bisect(&self, pred: impl Fn(&$ty) -> bool) -> $ty {
                                        let Range { start: mut ok, end: mut bad } = *self;
                                        if !pred(&ok) {
                                            return ok;
                                        }
                                        while bad - ok > 1 {
                                            let mid = ok + (bad - ok) / 2;
                                            *(if pred(&mid) { &mut ok } else { &mut bad }) = mid;
                                        }
                                        bad
                                    }
                                }
                                impl Bisect for RangeFrom<$ty> {
                                    type Input = $ty;
                                    type Output = $ty;
                                    fn bisect(&self, pred: impl Fn(&$ty) -> bool) -> $ty {
                                        let RangeFrom { start: ok } = *self;
                                        if !pred(&ok) {
                                            return ok;
                                        }
                                        let mut w = 1;
                                        while pred(&(ok + w)) {
                                            w *= 2;
                                        }
                                        (ok + w / 2..ok + w).bisect(pred)
                                    }
                                }
                                impl Bisect for RangeTo<$ty> {
                                    type Input = $ty;
                                    type Output = $ty;
                                    fn bisect(&self, pred: impl Fn(&$ty) -> bool) -> $ty {
                                        let RangeTo { end: bad } = *self;
                                        if pred(&bad) {
                                            return bad;
                                        }
                                        let mut w = 1;
                                        while !pred(&(bad - w)) {
                                            w *= 2;
                                        }
                                        (bad - w..bad - w / 2).bisect(pred)
                                    }
                                }
                            )* }
                        }
            impl_bisect_uint! { u8 u16 u32 u64 u128 usize }
            macro_rules! impl_bisect_int {
                            ( $( ($ity:ty, $uty:ty, $i2u:ident, $u2i:ident), )* ) => { $(
                                impl Bisect for Range<$ity> {
                                    type Input = $ity;
                                    type Output = $ity;
                                    fn bisect(&self, pred: impl Fn(&$ity) -> bool) -> $ity {
                                        let Range { start, end } = *self;
                                        let start = $i2u(start);
                                        let end = $i2u(end);
                                        $u2i((start..end).bisect(|&u| pred(&$u2i(u))))
                                    }
                                }
                                impl Bisect for RangeFrom<$ity> {
                                    type Input = $ity;
                                    type Output = $ity;
                                    fn bisect(&self, pred: impl Fn(&$ity) -> bool) -> $ity {
                                        let RangeFrom { start } = *self;
                                        let start = $i2u(start);
                                        $u2i((start..).bisect(|&u| pred(&$u2i(u))))
                                    }
                                }
                                impl Bisect for RangeTo<$ity> {
                                    type Input = $ity;
                                    type Output = $ity;
                                    fn bisect(&self, pred: impl Fn(&$ity) -> bool) -> $ity {
                                        let RangeTo { end } = *self;
                                        let end = $i2u(end);
                                        $u2i((..end).bisect(|&u| pred(&$u2i(u))))
                                    }
                                }
                                fn $i2u(i: $ity) -> $uty { !(!(0 as $uty) >> 1) ^ i as $uty }
                                fn $u2i(u: $uty) -> $ity { (!(!0 >> 1) ^ u) as $ity }
                            )* }
                        }
            impl_bisect_int! {
                (i8, u8, i2u8, u2i8),
                (i16, u16, i2u16, u2i16),
                (i32, u32, i2u32, u2i32),
                (i64, u64, i2u64, u2i64),
                (i128, u128, i2u128, u2i128),
                (isize, usize, i2usize, u2isize),
            }
            macro_rules! impl_bisect_float {
                            (
                                $(
                                    (
                                        $fty:ty, $ity:ty, $uty:ty, $w:literal,
                                        $f2u:ident, $u2f:ident, $mask:ident
                                    ),
                                )*
                            ) => { $(
                                impl Bisect for Range<$fty> {
                                    type Input = $fty;
                                    type Output = $fty;
                                    fn bisect(&self, pred: impl Fn(&$fty) -> bool) -> $fty {
                                        let Range { start, end } = *self;
                                        let start = $f2u(start);
                                        let end = $f2u(end);
                                        $u2f((start..end).bisect(|&u| pred(&$u2f(u))))
                                    }
                                }
                                impl Bisect for RangeFrom<$fty> {
                                    type Input = $fty;
                                    type Output = $fty;
                                    fn bisect(&self, pred: impl Fn(&$fty) -> bool) -> $fty {
                                        let RangeFrom { start } = *self;
                                        let start = $f2u(start);
                                        $u2f((start..).bisect(|&u| pred(&$u2f(u))))
                                    }
                                }
                                impl Bisect for RangeTo<$fty> {
                                    type Input = $fty;
                                    type Output = $fty;
                                    fn bisect(&self, pred: impl Fn(&$fty) -> bool) -> $fty {
                                        let RangeTo { end } = *self;
                                        let end = $f2u(end);
                                        $u2f((..end).bisect(|&u| pred(&$u2f(u))))
                                    }
                                }
                                fn $mask(u: $uty) -> $uty {
                                    ((u as $ity >> ($w - 1)) as $uty >> 1) | 1 << ($w - 1)
                                }
                                fn $f2u(f: $fty) -> $uty { f.to_bits() ^ $mask(f.to_bits()) }
                                fn $u2f(u: $uty) -> $fty { <$fty>::from_bits(u ^ $mask(!u)) }
                            )* };
                        }
            impl_bisect_float! {
                (f32, i32, u32, 32, f2u32, u2f32, mask32),
                (f64, i64, u64, 64, f2u64, u2f64, mask64),
            }
            impl<T> Bisect for [T] {
                type Input = T;
                type Output = usize;
                fn bisect(&self, pred: impl Fn(&T) -> bool) -> usize {
                    if self.is_empty() || !pred(&self[0]) {
                        return 0;
                    }
                    let mut ok = 0;
                    let mut bad = self.len();
                    while bad - ok > 1 {
                        let mid = ok + (bad - ok) / 2;
                        *(if pred(&self[mid]) { &mut ok } else { &mut bad }) = mid;
                    }
                    bad
                }
            }
        }
        #[allow(unused_imports)]
        pub use bisect::*;
    }
    pub mod math {
        pub mod linear_sieve {
            pub struct LinearSieve {
                lpf: Vec<usize>,
                lpf_e: Vec<(usize, u32)>,
                pr: Vec<usize>,
            }
            impl LinearSieve {
                pub fn new(n: usize) -> Self {
                    let mut lpf = vec![1; n + 1];
                    let mut pr = vec![];
                    for i in 2..=n {
                        if lpf[i] == 1 {
                            lpf[i] = i;
                            pr.push(i);
                        }
                        let lpf_i = lpf[i];
                        for &j in pr.iter().take_while(|&&j| j <= lpf_i.min(n / i)) {
                            lpf[i * j] = j;
                        }
                    }
                    let mut lpf_e = vec![(1, 0); n + 1];
                    for i in 2..=n {
                        let p = lpf[i];
                        let j = i / p;
                        lpf_e[i] = if lpf[j] == p { (lpf_e[j].0 * p, lpf_e[j].1 + 1) } else { (lpf[i], 1) };
                    }
                    Self { lpf, lpf_e, pr }
                }
                pub fn is_prime(&self, i: usize) -> bool { i >= 2 && self.lpf[i] == i }
                pub fn lpf(&self, i: usize) -> Option<usize> { (i >= 2).then(|| self.lpf[i]) }
                pub fn factors_dup(&self, i: usize) -> impl Iterator<Item = usize> + '_ {
                    std::iter::successors(Some(i), move |&i| Some(i / self.lpf[i]))
                        .take_while(|&i| i > 1)
                        .map(move |i| self.lpf[i])
                }
                pub fn factors(&self, i: usize) -> impl Iterator<Item = (usize, u32)> + '_ {
                    std::iter::successors(Some(i), move |&i| Some(i / self.lpf_e[i].0))
                        .take_while(|&i| i > 1)
                        .map(move |i| (self.lpf[i], self.lpf_e[i].1))
                }
                pub fn euler_phi(&self, i: usize) -> usize {
                    std::iter::successors(Some(i), move |&i| Some(i / self.lpf_e[i].0))
                        .take_while(|&i| i > 1)
                        .map(|i| self.lpf_e[i].0 / self.lpf[i] * (self.lpf[i] - 1))
                        .product()
                }
                pub fn euler_phi_star(&self, i: usize) -> usize {
                    match i {
                        0..=2 => i / 2,
                        _ => 1 + self.euler_phi_star(self.euler_phi(i)),
                    }
                }
                pub fn divisors(&self, i: usize) -> impl Iterator<Item = usize> + DoubleEndedIterator {
                    let mut res = vec![1];
                    for (p, e) in self.factors(i) {
                        let mut tmp = vec![];
                        let mut pp = 1;
                        for _ in 1..=e {
                            pp *= p;
                            tmp.extend(res.iter().map(|&x| x * pp));
                        }
                        res.extend(tmp);
                    }
                    res.sort_unstable();
                    res.into_iter()
                }
                pub fn divisors_count(&self, i: usize) -> usize {
                    self.factors(i).map(|(_, e)| e as usize + 1).product()
                }
                pub fn divisors_sum(&self, i: usize) -> usize {
                    std::iter::successors(Some(i), move |&i| Some(i / self.lpf_e[i].0))
                        .take_while(|&i| i > 1)
                        .map(|i| (self.lpf_e[i].0 * self.lpf[i] - 1) / (self.lpf[i] - 1))
                        .product()
                }
                pub fn primes(&self) -> impl Iterator<Item = usize> + DoubleEndedIterator + '_ {
                    self.pr.iter().copied()
                }
                pub fn dp<T>(
                    &self,
                    zero: T,
                    one: T,
                    eq: impl Fn(&T, usize) -> T,
                    gt: impl Fn(&T, usize) -> T,
                ) -> Vec<T> {
                    let n = self.lpf.len() - 1;
                    let mut res = vec![zero, one];
                    if n <= 1 {
                        res.truncate(n + 1);
                        return res;
                    }
                    res.reserve(n + 1);
                    for i in 2..=n {
                        let lpf = self.lpf[i];
                        let j = i / lpf;
                        let prev = &res[j];
                        let cur = if lpf == self.lpf[j] { eq(prev, lpf) } else { gt(prev, lpf) };
                        res.push(cur);
                    }
                    res
                }
            }
        }
        #[allow(unused_imports)]
        pub use linear_sieve::*;
    }
}

提出情報

コンパイルエラー

warning: unknown lint: `private_interfaces`
   --> src/main.rs:142:9
    |
142 | #[allow(private_interfaces)]
    |         ^^^^^^^^^^^^^^^^^^
    |
    = note: `#[warn(unknown_lints)]` on by default

ジャッジ結果