Submission #60558252

---

Source Code Expand

#[allow(unused_imports)]
use num_integer::Roots;
use proconio::input;

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

    let half_n = n.sqrt();
    let v = create_primes(half_n+1);
    let mut ans :usize = 0;
    let n = n as u64;

    for &vi in v.iter() {
        let val = vi.pow(8);
        if val > n { break; }
        ans += 1;
    }

    for i in 0..v.len() {
        let p = v[i].pow(2);
        let max_q = n / p;
        // v[j]^2 がmax_q以下である最大
        // -> v[j]^2がmax_q+1以上である最小
        let idx = v.binary_search_by_key(&(&max_q+1), |vi| vi.pow(2)).unwrap_or_else(|x|x);

        if i < idx {
            ans += idx - i - 1;
        } else {
            break;
        }
    }
    println!("{ans}");
}

pub trait Debuggable {
    fn debug_string(&self) -> String;
}

impl<T: std::fmt::Debug + std::fmt::Display> Debuggable for Vec<T> {
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        use std::iter::repeat;
        if let Some(max_size) = self.iter()
            .map(|x| format!("{:?}", x).len())
            .max() {
                let mut idx = String::from("idx |");   
                let mut val = String::from("val |");   
                for (i, xi) in self.iter().enumerate() {
                    idx.push_str(
                        &format!(" {:>w$} |", i, w=max_size)
                    );
                    val.push_str(
                        &format!(" {:>w$} |", xi, w=max_size)
                    );
                }

                format!("{}\n{}\n{}\n", idx, repeat('-').take(idx.len()).join(""), val)
            } else {
                format!("idx | \nval |\n")
            }
    }
}

impl<T: std::fmt::Debug + std::fmt::Display> Debuggable for std::collections::BTreeSet<T> {
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        format!("{{ {} }}", self.iter().join(", "))
    }
}

impl<T, U> Debuggable for std::collections::BTreeMap<T, U> 
where T: std::fmt::Debug + std::fmt::Display, U: std::fmt::Debug + std::fmt::Display
{
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        format!(
            "{{\n{}\n }}", self.iter()
                .map(|(k, v)| format!("{k} -> {v}, "))
                .join("\n")
        )
    }
}

// lg! マクロの定義
#[macro_export]
macro_rules! lg {
    ($val:expr) => {
        #[cfg(feature = "local")]
        {
            {
                use Debuggable;
                let val = &$val;
                eprintln!(
                    "[{}:{}] {} = \n{}",
                    file!(),
                    line!(),
                    stringify!($val),
                    val.debug_string()
                );
                val
            }
        }
    }
}
    // 素因数分解
/* n = 1e12ぐらいまでじゃないとTLEするので注意 */
pub fn prime_factorization(n: u64) -> std::collections::BTreeMap<u64, u64> {
    let mut res = std::collections::BTreeMap::new();

    let mut i = 2;
    let mut k = n;
    while i * i <= n {
        let mut cnt = 0;
        while k % i == 0 {
            k /= i;
            cnt += 1;
        }
        if cnt != 0 {
            res.insert(i, cnt);
        }
        i += 1;
    }

    if k != 1 {
        res.insert(k, 1);
    }

    res
}

/* nまでの素数を生成して配列で返す */
pub fn create_primes(n: usize) -> Vec<u64> {
    let mut res = vec![];
    let mut ck = vec![false; n];

    let mut i = 2;
    while i < n {
        if !ck[i] {
            res.push(i as u64);
            let mut j = i;
            while j < n {
                ck[j] = true;
                j += i;
            }
        }
        i += 1;
    }

    res
}

// 約数全列挙
pub fn divisors(n: u64) -> Vec<u64> {
    let mut res = vec![];
    let mut i = 1;
    while i * i <= n {
        if n % i == 0 {
            res.push(i);
            if i != n / i && i != 1{
                res.push(n / i);
            }
        }
        i += 1;
    }
    res
}

Submission Info

Judge Result