アルゴリズムと数学 068

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