AtCoder Beginner Contest 356 E

https://atcoder.jp/contests/abc356/tasks/abc356_e

なので、そこまでの値がいくつあるかを調べます。分母がnなら分子が[nq, n(q+1))の範囲なら値がqになります。

// Max/Min
#![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()
}


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

fn read_input() -> Vec<usize> {
    let _N: usize = read();
    let A: Vec<usize> = read_vec();
    A
}

fn frequency(A: Vec<usize>) -> Vec<usize> {
    let M: usize = 1000000;
    let mut B: Vec<usize> = vec![0; M+1];
    for a in A.into_iter() {
        B[a] += 1
    }
    B
}

fn accumulate(B: &Vec<usize>) -> Vec<usize> {
    let M = B.len() - 1;
    let mut acc: Vec<usize> = vec![0; M+1];
    for n in 1..M+1 {
        acc[n] = acc[n-1] + B[n]
    }
    acc
}

use std::cmp::min;

fn F(A: Vec<usize>) -> usize {
    let B = frequency(A);
    let acc = accumulate(&B);
    let M = acc.len() - 1;
    let mut s: usize = 0;
    for n in 1..M+1 {
        if B[n] == 0 {
            continue
        }
        for q in 1..(M/n)+1 {
            s += q * B[n] * (acc[min(n*(q+1)-1, M)] - acc[n*q-1])
        }
        s -= B[n] * (B[n] + 1) / 2
    }
    s
}

fn main() {
    let A = read_input();
    println!("{}", F(A))
}