Submission #54134771

---

Source Code Expand

use std::cmp::min;

use proconio::input;

fn main() {
    // N
    // A_1 A_2 .. A_N
    input! {
        n: usize,
        mut a: [u64; n],
    }
    a.sort();
    let max_a = a[n - 1];
    let mut valcount = vec![0; max_a as usize + 1];
    for i in 0..n {
        valcount[a[i] as usize] += 1;
    }
    let mut cum_valcount = vec![0; max_a as usize + 1];
    for i in 1..max_a as usize + 1 {
        cum_valcount[i] = cum_valcount[i - 1] + valcount[i];
    }
    // println!("{:?}", valcount);
    // println!("{:?}", cum_valcount);
    let mut ans = 0;
    let mut prev = 0;
    let mut prev_ans = 0;
    for i in 0..n {
        let cur = a[i];
        if cur == prev {
            prev_ans -= 1;
            // println!("i: {}, prev_ans:{} ", i, prev_ans);
            ans += prev_ans;
        } else {
            prev = cur;
            prev_ans = 0;
            for d in 1..=max_a / cur {
                let from = min(d * cur, max_a + 1);
                let to = min((d + 1) * cur - 1, max_a);
                let count = cum_valcount[to as usize] - cum_valcount[from as usize - 1];
                // println!("i: {}, d:{} count:{} ", i, d, count);
                if count > 0 {
                    prev_ans += d * count;
                }
            }
            prev_ans -= 1; // Remove A[i]/A[i] pair
                           // println!("i: {}, prev_ans:{} ", i, prev_ans);
            ans += prev_ans;
        }
    }
    println!("{}", ans);
}

Submission Info

Judge Result