AtCoder Beginner Contest 361 F

https://atcoder.jp/contests/abc361/tasks/abc361_f

これは昔からよく見る問題です。
として、2乗で表せる整数は、3乗で表せる整数はなどとなります。しかし、例えばなどと重複するのでそのまま数えてはいけないです。そこで底をべき乗で表されないものに限定します。64ならとします。そうすると、2乗で表せる整数はに限定され、3乗で表せる整数はとなります。一般にを1を除いたNまでのべき乗数とすると、

と書けます。
しかし、Pythonなら簡単なのですが、Rustだと簡単にオーバーフローするので累乗根の計算が難しいんです。なので、ならがになるので、そこはまとめて計算します。そうすると累乗根の計算が楽になります。

// x = a^b
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// library ////////////////////

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

// floor(x^(1/e))
fn root(x: i64, e: u32) -> i64 {
    let next_y = |y: i64| {
        (x / y.pow(e-1) + (e as i64 - 1) * y) / (e as i64)
    };
    
    let mut y = (x as f64).powf(1.0 / (e as f64)) as i64;
    if y.pow(e) < x {
        y = next_y(y)
    }
    loop {
        let y1 = next_y(y);
        if y <= y1 {
            break
        }
        y = y1
    }
    y
}

fn floor_log(n: i64, b: i64) -> u32 {
    if n < b {
        0
    }
    else {
        1 + floor_log(n / b, b)
    }
}


//////////////////// process ////////////////////

fn f(n: i64, memo: &mut HashMap<i64, i64>) -> i64 {
    if n < 4 {
        return 0
    }
    else if let Some(m) = memo.get(&n) {
        return *m
    }
    
    let mut s: i64 = 0;
    let mut e_mid: u32 = 0;
    for b in 2.. {
        let e1 = floor_log(n, b);
        if e1 <= 2 {
            e_mid = e1;
            break
        }
        
        let e2 = floor_log(n, b+1);
        s += ((e1 - e2) as i64) * (b - 1 - f(b, memo));
        if e1 == e2 + 1 {
            e_mid = e2;
            break
        }
    }
    
    for e in 2..e_mid+1 {
        let r = root(n, e);
        s += r - 1 - f(r, memo)
    }
    
    memo.insert(n, s);
    s
}

fn F(N: i64) -> i64 {
    let mut memo: HashMap<i64, i64> = HashMap::new();
    f(N, &mut memo) + 1
}

fn main() {
    let N: i64 = read();
    println!("{}", F(N))
}