D - Small GCD / Codeforces Round 911 (Div. 2)

問題

整数 に対して、関数 を「 となるように並び替えたときの の値」を返す関数として定義する。

要素数が 個の整数列 が与えられるので、 であるすべての に対して の値の総和を求めよ。

すなわち、 の値を求めよ。

入力

まず最初の1行目に、テストケースの個数を表す整数 が与えられる。

その後、 個のテストケースのそれぞれに対して、以下のように入力が与えられる。

• 最初の1行目には、整数 が与えられる。
• 次の1行には、 個の整数列 の要素が順に与えられる。

条件

• 
• 
  • すべてのテストケースにおける の値の合計は を超えない。
• 

出力

各テストケースでの答えを1行ごとに出力すること。

解法

まずはすべての の組み合わせについて を求めるという方法が思いつきますが、これは の計算量がかかり、 であるので実行時間制限に間に合いません。

ここで、 を「 のうち、値が の倍数であるものの個数」、 を「 の値が の倍数となる の組み合わせの個数」として定めます。

また、数列 を昇順に並び替えることとします。

ここで、 の情報が について入っているものとします。 このとき、 の値があることにより、 がどのように更新されるかということを考えます。

まず、 は「 の値が の倍数となる の個数」と定義しました。 また、 は のときの の値として定義されています。

そのため、 としたときに、 の値として存在するであろうものとして考えられるのは、 の約数です。 を の約数とするとき、この状態で となるような の値の組み合わせの個数は

• については で計算されている
• については が昇順で並んでいることから の 個が考えられる

ということから、 個であると計算が行えます。

従って、 の値については のすべての約数 について として更新していくことにより、 についての情報を足せるということが言えます。

この の値が更新された状態で、 のすべての約数 に対して と更新すれば、 についても の情報を足せると言えます。

以上から、ソートされた数列 について、 の順に、 のそれぞれを更新していくことにより、数列 全体での を算出できます。

さて、ここで、 が 「 となる の個数」であれば、 より の値も最大で であることから求める総和は \begin{align} \displaystyle \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} \sum_{k = j + 1}^{n} f({a}_{i}, {a}_{j}, {a}_{k}) = \sum_{x = 1}^{{10}^{5}} x \cdot \mathrm{sum}_{x} \end{align} として算出することができます。

しかし実際には、 は の値が の倍数となる の個数なので、このように単純に計算するのみでは正しい答えとはなりません。

例えば、 となる の組が存在する場合、この組の存在によって のうち の部分で1組分が加算されることになります。

ここで、 の値が大きければ大きいほど、「値が の倍数となるものの個数」と「値が となるものの個数」が等しくなる、ということに注目します。

そのため の値を「 となる の個数」として扱うために、 を大きい順に見ていき、答えに の値を加えたら、 のすべての約数 に対して と値を更新することを考えます。

この作業を行うことにより、 を大きい順に見ているため、該当する を見る頃には「いま見ている は考えられる値の中で最大値」ということになるため、更新されていった の値は「値が となるものの個数」となります。

従って、この作業を の順に行うことにより、 の値の総和を求めることができます。

以上をまとめると、

1. 数列 を昇順にソートする
2. に対して以下の作業を繰り返し行う
   • のすべての約数 に対して、 と更新する
   • の更新後、 のすべての約数 に対して、 と更新する
3. に対して以下の作業を繰り返し行う
   • 答えとなる値に を足す
   • のすべての約数 に対して、 と更新する

という3つの手順で総和を求めることができます。

整数 の約数の個数を とおくと、これは の計算量で求めることができ、 から までの整数の約数の個数の総和は 個なので、これは実行時間制限に間に合うと考えられます。

ただし、整数 のすべての約数を毎回計算で求めていると、この方法では実行時間制限を超えてしまう可能性があります。 そのため、 である整数 のすべての約数を予め求めて保存しておくことを考えます。

ここで、ある整数 がある素数 を素因数に持っているとき、 の約数は「 の約数すべてと、 の約数すべてに を掛けた整数すべて」の中から重複を除いたもの、ということになります。

このことから、C++の set 等のデータ構造を用いて、小さい順に整数 の約数を計算していくことで、 であるすべての整数の約数を求めて保存することができると言えます。

ソースコード

まず、ある整数の約数をすべて求める prepare_divisors() 関数を以下のように実装しました。

bool visited[int(1e5 + 5)]; // visited はすでにその整数の約数を計算したかどうかを管理する
set<int> divisors[int(1e5 + 5)]; // divisors[i] は整数 i のすべての約数が入る

void prepare_divisors(int num) { // 整数 num の約数を求めて divisors[num] に保存する
  if (visited[num]) { // もし num の約数を既に求めていたら、何もせず return する
    return;
  }

  visited[num] = true; // num の約数を既に求めたことにする
  for (int i = 2; i * i <= num; i++) {
    if (num % i != 0) {  // num の最小の素因数を探す
      continue;
    }

    // i が整数 num の素因数のとき
    prepare_divisors(num / i); // 整数 (num / i) の約数を求める
    auto iter = divisors[num / i].begin(); // 整数 (num / i) の約数を順番に見る
    while (iter != divisors[num / i].end()) {
      divisors[num].insert(*iter); // (num / i) の約数を divisors[num] にも入れる
      divisors[num].insert(*iter * i); // (num / i) の約数を i 倍したものも divisors[num] に入れる
      iter++;
    }
    break; // これ以上 for ループを回す必要がないので break する
  }

  // num が素数の場合も考慮して、 1 と num を改めて divisors[num] に入れる
  divisors[num].insert(1);
  divisors[num].insert(num);
  return;
}

上記の prepare_divisors() により から までのすべての整数の約数が取り出せる状態になった上で、求める総和を返す solve() 関数を以下のように実装しました。

set<int> divisors[int(1e5 + 5)];
ll n, a[int(1e5 + 5)], cnt[int(1e5 + 5)], sum[int(1e5 + 5)];

ll solve() {
  // 値の入力
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1); // 数列 a をソートする（手順1）

  // a[1] から a[n] の順に、手順2を実行する
  for (ll i = 1; i <= n; i++) {
    auto iter = divisors[a[i]].begin();
    while (iter != divisors[a[i]].end()) {
      sum[*iter] += cnt[*iter] * (n - i); // a[i] の約数に対して、 sum の値を更新する
      cnt[*iter]++; // a[i] の約数に対して、 cnt の値を更新する
      iter++;
    }
  }

  ll ans = 0; // 答えとなる総和

  // 10^5 から 1 の順に、手順3を実行する
  for (ll i = ll(1e5); i >= 1; i--) {
    ans += i * sum[i]; // 答えに i * sum[i] の値を足す
    auto iter = divisors[i].begin();
    while (iter != divisors[i].end()) {
      sum[*iter] -= sum[i]; // i の約数に対して、 sum の値を更新する
      iter++;
    }
  }

  return ans;
}

• 提出したコード: https://codeforces.com/contest/1900/submission/237853465
• GitHub

感想

非常にボリュームのある問題だったと思います。自力で解けて嬉しいです。