[ABC206] E - Divide Both

[Q] https://atcoder.jp/contests/abc206/tasks/abc206_e

・考察
0. とるペアは(x < y)として選ぶ。最後にswap分の2倍をする予定。
1. 倍数を固定したときに何通りとれるかを考える。それぞれの倍数でnC2通りずつ。
この時点では、(x, y)に対してg = xになる場合をいったん考慮しない。
2. 2の倍数を選んだ時に、実はgcd=4でした、みたいな(4, 8)とかを除く。
cnt[g] -= cnt[g*2] + cnt[g*3] + …をすればいい。
3. 2 ~ Rの倍数を加算していけばいい。
4. だけど、(x, y)でg==xの場合を除く。これは、倍数の個数-1個。
2,4,6,8が候補だとして、2をとる組み合わせを除くので。4,6,8の3個。

・実装

int main() {
  cincout();
  
  ll L, R;
  cin >> L >> R;
  vector<ll> cnt(R + 10, 0);
  // 1. 倍数を固定したときに、何通りとれるか。それぞれnC2通り
  for(ll i = R; i > 1; --i){ // 降順必須
    ll c = R / i - (L - 1) / i;
    cnt[i] = c * (c - 1) / 2;
    ll g = i * 2;
    // 2. より大きいgでとれるものを省く
    while (g <= R){
      cnt[i] -= cnt[g];
      g += i;
    }
  }
  
  ll ans = 0;
  for(ll i = 2; i <= R; ++i){
    ll c = R / i - (L - 1) / i;
    // 3. i==gになっている場合を除く
    if (i >= L && i <= R){ 
      cnt[i] -= c - 1;
    }
    ans += cnt[i];
  }
  // 0. swap分の2倍
  cout << (ans * 2) << endl;
}

https://atcoder.jp/contests/abc206/submissions/37966450