あらこま日記

よろしく

ABC125C - GCD on Blackboard(300)

AtCoder Python gcd 累積

解いた問題で面白かったものについて書いていくことにしました。
今の自分は300点（ABCがABCDまでの時）が解けるか解けないかってかんじなので、当分はそのへんの問題が多くなりそうです。

問題

atcoder.jp 【概要】
N個の整数 $A_1,A_2,...,A_N$ がある。
この中から1つ選んで好きな整数（1以上10**9以下）に書き換えてもよい。
書き換えた後のN個の整数の最大公約数の最大値を答える。

【制約】

入力は全て整数。
$2\leq N\leq 10^{5}$
$1\leq A_i\leq 10^{9}$

考える

何を1個だけ書き換えても、残りのN-1個でのgcdより大きくならなそう。
N-1個でのgcdに書き換えるとすると、整数1個を取る（消す）のと同じ。
（愚直に1個ずつ消してgcdとっていくのはTLEでしょ…？）

結局自力ACできず…

解説見る

複数個の整数でgcdをとるとき、どのペアから始めても結果は同じになる。
なので、整数Aiの「左側( $A_{0\sim i-1}$ )でのgcd」と「右側( $A_{i+1\sim}$ )でのgcd」とでgcdをとれば、Aiを消した時の結果が得られる。すべてのAiについて求めた中の最大が答え。と考える。
⇒累積和みたいにgcdを左端からと右端からとの2通りとっていき、それぞれlistに保持することでこれを実装できる。

ACコード（python）

Submission #7352699 - AtCoder Beginner Contest 125

N = int(input())
A = list(map(int, input().split()))

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

L = [0] * (N+1)
R = [0] * (N+1)
for i in range(1, N+1):
    L[i] = gcd(L[i-1], A[i-1])
for i in range(N)[::-1]:
    R[i] = gcd(R[i+1], A[i])

M = [gcd(L[i], R[i+1]) for i in range(N)]

print(max(M))

おわりに

初めてTeX書いたけどめっちゃ時間かかった…。
次も書くかは謎(?)。