ABC136E - Max GCD

問題概要

リンク

長さ$N$の整数列$A_1,A_2,\cdots A_N$と$K$が与えられる。

以下の操作を$K$回まで行い、整数列を加工できる。

• $1 \leq i,j \leq N$を満たす$i,j$を選び、$A_i$に 1 を足し、$A_j$から 1 を引く。

この操作によって整数列を加工後、$A_1,...,A_N$の共通の約数で最大のものを求めよ。

制約

$2 \leq N \leq 500$

$1 \leq A_i \leq 10^{6}$

$0 \leq K \leq 10^{9}$

解法

この問題のポイントは以下の 2 つ。

• どのような性質を満たす数が解の候補となるか
• 解の候補となった数が条件を満たすことをどのように判定するか

どのような性質を満たす数が解の候補となるか

加工後の整数列を$A'_1,A'_2,\cdots A'_N$とし、性質を見てみる。 整数列$A_1,A_2,\cdots A_N$に対して行える操作は、どこかを 1 増やし、どこかを 1 減らすことなので、数列全体の値の合計は変化しない。よって$\sum_{i=1}^{N} A_i = \sum_{i=1}^{N} A'_i$が成り立つ。

また、全ての$A'_i$はこの問題の解となるある数$x$の倍数になっているので、適当な数を$a$とすると$\sum_{i=1}^{N} A'_i = a \times x$と表すことができる。よって、$\sum_{i=1}^{N} A_i = \sum_{i=1}^{N} A'_i = a \times x$となる。

このことから、求めたい数$x$は、$A_1,...,A_N$の総和$\sum_{i=1}^{N} A_i$の約数の中にあることが分かった。

自然数$n$の約数は、下記のような方法で$O(\sqrt n)$で列挙することができる。

fn enumerate_divisor(n: usize) -> Vec<usize> {
    let mut i = 1;

    let mut divisors = vec![];

    // 2乗してn以下になる数を列挙する
    while i * i <= n {
        // その数iがnを割り切る場合、iとn/iはnの約数となる
        if n % i == 0 {
            divisors.push(i);
            divisors.push(n / i);
        }
        i += 1;
    }

    divisors
}

条件を満たすことをどのように判定するか

解の候補$x$を用意した時、全ての$A'_i$を$x$の倍数にするために何回操作が必要なのかを考える。これが分かれば、解の候補を大きい順に見ていき、$K$回以下の操作で作ることができることが判明したらその時の$x$が求める答えとなる。

まずは問題で定義されている操作を無視し、$A_i$に何かを足したり引いたりして最小の増減で$x$の倍数に変形するためにはどうすればいいか考える。これは、$A_i + d$を$x$で割った時の余りが 0 になるようにうまく値を調整することで下記の 2 通りのどちらかで実現できる。

• $A_i$ から何かを引いて$x$の倍数にする場合は、$A_i {\rm mod} x$の値を$A_i$から引く。 (以後 マイナス 型と呼ぶ)
• 逆に$A_i$ に何かを足して$x$の倍数にする場合は、$x - A_i {\rm mod} x$を$A_i$に足す。 (以後 プラス 型と呼ぶ)

このように$x$の倍数にするために必要な最小の増減量は分かったが、問題で定義されている操作と等価にするには、全ての$A_i$に対する増減の総和が 0 になっている必要がある。次はどうやってこの帳尻を合わせるのかを考える。

$d_i$を$A_i + d_i = A'_i$となる数とした時、$\sum_{i=1}^{N} d_i = 0$となる。 マイナス 型であれば$d_i = - A_i {\rm mod} x$、プラス 型であれば$d_i = x - A_i {\rm mod} x$である。マイナス 型と プラス 型の違いは$x$の部分のみなので、$\sum_{i=1}^{N} d_i$は、プラス 型を選択した回数を$a$として

$\sum_{i=1}^{N} d_i = a \times x - \sum_{i=1}^{N} A_i {\rm mod} x$

と表されることが分かる。$x$が$\sum_{i=1}^{N} A_i$の約数という前提で考えると、$0 \leq b \leq N$となるある$b$に対して

$\sum_{i=1}^{N} A_i {\rm mod} x = b \times x$

が成り立つ。この$b$は$\sum_{i=1}^{N} A_i {\rm mod} x$を$x$で割ることで求めることができる。

$\sum_{i=1}^{N} d_i = a \times x - b \times x$となるため、$a = b$とすればよい。これでプラス型を選択する回数$a$を特定できた。

あとはどの$i$で合計$a$回のプラス型を選択するかだが、これは単に$x - A_i {\rm mod} x$が小さいもの、つまり$A_i {\rm mod} x$が大きい順に$i$を並べた時の最初の$a$個とすればよい。

プラス型かマイナス型の$d_i$を記録しておくことで、「$1 \leq i,j \leq N$を満たす$i,j$を選び、$A_i$に 1 を足し、$A_j$から 1 を引く」操作の回数も分かるので、$K$回以下の操作で全ての$A'_i$を$x$の倍数にできるかを判定できる。

まとめ

$\sum_{i=1}^{N} A_i$の約数が解の候補となる。解の候補である各$x$に対し、$K$回の操作で各$A'_i mod x = 0$が構成できるかを調べる。調べる方法は下記の通り。

• $a = (\sum_{i=1}^{N} A_i {\rm mod} x) / x$を計算し、必要なプラス 型の回数を調べる。
• $A_i {\rm mod} x$が大きい順に$i$を並べ、その順に$a$個の$x -A_i {\rm mod} x$を足し合わせたものが必要な操作の回数になる。

必要な操作の数が$K$回以下の最大の$x$が解となる。