Max/Min の解説

まずソートしておく。 次に分母つまりはminを固定方針を立てる。 すると、ソートしているので固定したminより右にある数がmaxとなる候補となって、考えやすくなる。

ここで、制約から調和級数をエスパーする。

すると、各ループ(下実装でloopでかいてあるところ)で、floorの答えの数が1ずつ増えていくだけなので、これで求まることがわかる。 num..num + kukan の範囲に何個数があるかは累積和を用いて前計算しておく。

ただ、同じ数がややこしいので、その分はあらかじめ、nc2通りを計算しておいて、ループの中では処理しないように気をつける。

何も考えずにセグ木を用いると、log * logになって重い。(600ms)

累積和を用いると50msくらいでとおる。

fn main() {
    input! {
        n: usize,
        a: [usize; n]
    }
    let &amax = a.iter().max().unwrap();
    let mut count = vec![0; amax + 1];
    for &num in a.iter() {
        count[num] += 1usize;
    }
    let mut ans = 0;
    for &num in count.iter() {
        if num <= 1 {
            continue;
        }
        ans += num * (num - 1) / 2;
    }
    
    let pref = PrefixSum1D::new(&count);
    for (num, &count) in count.iter().enumerate() {
        if num == 0 {
            continue;
        }
        let mut now = num;
        let mut cur = 0;
        let mut c = 1;
        loop {
            if now > amax {
                break;
            }
            let left = max(now, num + 1);
            let right = min(amax + 1, now + num);
            let tt = pref.range_sum(left..right);
            cur += c * tt;
            now += num;
            c += 1usize;
        }
        ans += cur * count;
    }
    println!("{}", ans);
}