[AtCoder] ABC 125 C – GCD on Blackboard

2019年5月17日

問題

方針

最大公約数の性質

関数 \( f(\cdot) \) を最大公約数を求める関数とします。ここで、\(f(x, y)\) は \( x, y \) の最大公約数とし、\( f(x, y, z) \) は \( x, y, z\) の最大公約数とします。

配列 \( A \) の最大公約数を \( g \) とします。\( g \) を 求めるのには、\( g = f(A) \) の計算は、\( g_i = f(g_{i – 1}, A_i) \) を計算すると、\( g = g_n \) が得られます。ここで、\( g_0 = 0 \) となることに注意します。上記の例でいうと、\( g = f(x, y, z) = f(f(x, y), z) \) となります。

配列の最大公約数は順序によらずに求めることができるので、次の式が成り立ちます。

\[ f(f(x, y), z) = f(x, f(y, z))\]

最大公約数の性質の応用

この問題では、一つだけ値を変えられることができますが、どの値にするかは関係ありません。つまり、配列の中で一つだけ値を消して最大公約数を計算することが求められます。ここで、配列の要素番号 \( i \) を除いた配列の最大公約数を \( k_i = f(A_1, A_2, \cdots, A_{i-1}, A_{i+1}, \cdots, A_{N} ) \) とします。これをすべての \( i \) について効率よく求める必要があります。

最大公約数の性質を利用して、次のように求めることができます。

\[ k_i = f(f(A_1, A_2, \cdots, A_{i-1}), f(A_{i+1}, \cdots, A_{N})) \]

\( f(A_1, A_2, \cdots, A_{i-1}) \) は配列の前からの最大公約数を計算していったものであり、もう一方は、\( f(A_{i+1}, \cdots, A_{N}) = f(A_N, A_{N – 1}, \cdots, A_{i+1})\) なので、配列の後ろから計算していったものです。これらは、累積和のようにしてあらかじめ計算しておくことができます。

コード

提出したコード

最大公約数の計算

int gcd(int m, int n) {
  if (n == 0) return m;
  else return gcd(n, m % n);
}

int L[N + 1];
int R[N + 1];
L[0] = 0;
R[0] = 0;
for (int i = 0; i < N; i++) {
  L[i + 1] = gcd(L[i], A[i]);
  R[i + 1] = gcd(R[i], A[N - i - 1]);
}
int ans = 0;
for (int i = 0; i < N; i++) {
  ans = max(ans, gcd(L[i], R[N - i - 1]));
  ans = max(ans, gcd(L[N - i - 1], R[i]));
}

感想

最大公約数の性質については知っていましたが、累積和を使うような方法は分かりませんでした。