ABC125 C - GCD on Blackboard - ペンギンかっこいい

備忘録

問題

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    left = [0] * (N + 1)
    right = [0] * (N + 1)

    # 予めGCDを計算する
    for i in range(N):
        # 左から累積したGCD
        left[i+1] = math.gcd(left[i], A[i])
    for i in reversed(range(N)):
        # 右から累積したGCD
        right[i] = math.gcd(right[i+1], A[i])

    ret = 0
    for i in range(N):
        ret = max(ret, math.gcd(left[i], right[i+1]))
    print(ret)

    
if __name__ == '__main__':
    main()

考え方

予め、左と右から累積したGCDを計算しておく。
累積したGCDからある整数を１つ省いた場合のGCDを求める。

まず、整数を書き換えることについて考える。
ある整数１つをどのような値にも書き換えることが可能なとき、
選んだ整数以外の整数で求められたGCDと同じ値にすることで、
GCDを最大にすることができる。

つまり、ある整数を書き換えた後の値は重要ではなく、
どの整数を選択するかだけを考えればよい。
選択した整数は省くことが出来ると考え、
選択した整数以外のGCDを求めるように考える。

ある１つの整数を省いたGCDを求めるために、
左から累積させたGCDと、右から累積させたGCDを利用する。

複数の値のGCDを求めるとき、
どのような順番で求めても答えが一意になる。
そのため、左から累積させたGCDと右から累積させたGCDを利用することで、
整数列からある１つの値を省いたときのGCDを求めることが出来る。

# 与えられる整数が[12, 15, 18]のとき、
left = [0, 12, 3, 3] # 左から累積させたGCD
right = [3, 3, 18, 0] # 右から累積させたGCD
# となる。

# 累積させたGCDから順(0 <= i < N)にGCDを求めることで
# ある整数を省いた場合のGCDを求めることが出来る
for i in range(N):
    math.gcd(left[i], right[i+1])
    # math.gcd(0, 3) -> math.gcd(0, math.gcd(15, 18)) 12を考慮しない場合
    # math.gcd(12, 18) -> math.gcd(12, math.gcd(18, 0)) 15を考慮しない場合
    # math.gcd(3, 0) -> math.gcd(math.gcd(12, 15), 0) 18を考慮しない場合

よくわかる解説
AtCoder ABC 125 C - GCD on Blackboard (300 点) - けんちょんの競プロ精進記録