#![allow(non_snake_case)] #[allow(unused_imports)] use proconio::{fastout, input, marker::*}; #[fastout] fn main() { input! { N: usize, } let mut buffer = vec![0.0; 10_000_010]; solve(N, &mut buffer); println!("{}", buffer[N]); } fn solve(m: usize, buffer: &mut [f64]) { if m == 1 { return; } let mut w = 0.; for i in 1..m { let g = gcd(i, m); if buffer[g] == 0. && g != 1 { solve(g, buffer); } w += buffer[g]; } buffer[m] = w / (m - 1) as f64 + m as f64 / (m - 1) as f64; } fn gcd(a: usize, b: usize) -> usize { if a < b { return gcd(b, a); } if b == 0 { return a; } else { return gcd(b, a % b); } }