#![allow(non_snake_case)] #[allow(unused_imports)] use proconio::{fastout, input, marker::*}; #[fastout] fn main() { input! { N: u32, } let mut sieve = vec![vec![]; 10_000_010]; for p in 2u32..=10_000_000 { if sieve[p as usize].is_empty() && gcd(p, N) != 1 { for q in (p * 2..10_000_010).step_by(p as usize) { sieve[q as usize].push(p); } } } let mut dp = vec![0.; 10_000_010]; for k in 2u32..=N { let mut s = 0.; for &d in sieve[k as usize].iter() { if sieve[k as usize].len() == 1 { s += dp[d as usize]; } else if d == sieve[k as usize][0] { let m = sieve[k as usize][1]; s += dp[d as usize] * (m - 1) as f32; } else { let m = sieve[k as usize][0]; s += dp[d as usize] * (m - 1) as f32; } } dp[k as usize] = s; dp[k as usize] /= (k - 1) as f32; dp[k as usize] += (k) as f32 / (k - 1) as f32; } println!("{}", dp[N as usize]); } fn gcd(a: u32, b: u32) -> u32 { if a < b { return gcd(b, a); } if b == 0 { return a; } else { return gcd(b, a % b); } }