AtCoder Beginner Contest 125 C - GCD on Blackboard

1月以来このブログ放置してたけど、ABCが思いのほか早く全完できたので解説記事を書いております。

atcoder.jp

問題概要

自然数の要素N個をもつ配列Aがある。
この中のひとつの要素を好きな数に書き換えて、N個の要素の最大公約数をできるだけ大きくしたい。

制約
2 ≤ N ≤ 10^5
1 ≤ Ai ≤ 10^9

解法

答えはAのどれかの要素の約数なので、答えの候補として（いっぱい約数がありそうな）max(A)の約数を列挙して配列Pに入れ、Aの要素それぞれがそれ（max(A)の約数）を約数に持つかチェックしていき、約数に持たないようなのが一つ以下であればそれを書き換えれば良い……と思って提出したのだけどWA。これは
N = 2
A = [2, 5]
で答え1になってしまう（P = [1] だが、5を2に書き換えれば正しい答えの2にできる）ので駄目だと気づいた。

そこで「一つしか書き換えられないので、答えはAの中で最大のものと2番めに大きいものどちらかの約数である必要がある」
と気づき、Aの中で最大のものと2番めに大きいものそれぞれの約数を配列Pに入れて上記の作業をしてAC。

（今考えてみると任意の異なる2つの要素であればいいので最大のものと2番めに大きいものでなくてよい、あとPの要素を大きい方から見ていって条件を満たせば出力して打ち切り、でよかった）

クソ汚いコード。

import math

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

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

M = A[-1]
P = [1,M]
for k in range(2,math.ceil(math.sqrt(M))+1):
    if M % k == 0:
        P.append(k)
        P.append(M//k)

M = A[-2]
P.append(M)
for k in range(2,math.ceil(math.sqrt(M))+1):
    if M % k == 0:
        P.append(k)
        P.append(M//k)

P = set(list(P))
ans = 1
for p in P:
    t = 0
    for k in range(N):
        if A[k]%p != 0:
            t += 1
        if t == 2:
            break
    if t <= 1:
        ans = max(ans,p)

print(ans)