https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_be
これも包除原理ですね。
Vecのスライスを使うと書きやすいようです。
// Number of Multiples 2 #![allow(non_snake_case)] //////////////////// 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() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>().split_whitespace() .map(|e| e.parse().ok().unwrap()).collect() } fn gcd(n: i64, m: i64) -> i64 { if m == 0 { n } else { gcd(m, n % m) } } //////////////////// process //////////////////// fn read_input() -> (i64, Vec<i64>) { let v = read_vec(); let N = v[0]; let V = read_vec(); (N, V) } fn g(N: i64, V: &[i64]) -> Vec<i64> { if V.len() == 1 { vec![-V[0]] } else { let mid = V.len() / 2; let ns1 = g(N, &V[..mid]); let ns2 = g(N, &V[mid..]); let mut ns = ns1.to_vec(); ns.extend(ns2.to_vec()); for n1 in ns1.into_iter() { for n2 in ns2.iter() { let n = n1 * n2 / gcd(n1.abs(), n2.abs()); if -N <= n && n <= N { ns.push(n) } } } ns } } fn f(N: i64, V: Vec<i64>) -> i64 { let ns = g(N, &V[..]); ns.into_iter().map(|n| if n > 0 { -(N/n) } else { N/-n }).sum::<i64>() } fn main() { let (N, V) = read_input(); println!("{}", f(N, V)) }