ABC125 C GCD on BalckBoard

i 番目の要素だけを除いた全体のGCDを求めるという愚直な案を書いて当然TLEだったので供養。

def gcd(x, y):
    xx = 0; yy = 0
    if x >= y:
        xx = x; yy = y
    else:
        xx = y; yy = x
    while yy > 0:
        xx, yy = yy, xx%yy
    return xx


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = 1
    for i in range(n):
        tmp = -1
        for j in range(n):
            if j == i:
                continue
            if tmp == -1:
                tmp = a[j]
            tmp = gcd(tmp, a[j])
        ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

ユークリッドの互除法の計算量がO(log(min(A,B))なので、これだとO(n^2log(min(A,B))となってTLE。

解答を見ると、結合則を使って、左右のを求めて、最後に計算。といった具合だろうか。

def gcd(x, y):
    xx = 0; yy = 0
    if x >= y:
        xx = x; yy = y
    else:
        xx = y; yy = x
    while yy > 0:
        xx, yy = yy, xx%yy
    return xx


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = 1
    # gcd の結合則を利用する(X, Y, Zがありgcd(gcd(x,y),z)==gcd(x,gcd(x, y)))
    l = [0 for i in range(n)]
    r = [0 for i in range(n+1)]
    for i in range(n-1):
        l[i+1] = gcd(l[i], a[i])
    for i in range(n-1, -1, -1):
        r[i] = gcd(r[i+1],a[i])
    for i in range(n):
        ans = max(ans, gcd(l[i], r[i+1]))
    print(ans)


if __name__ == '__main__':
    main()

これでAC出た。 結合則を用いて左右から計算していく発想は出なかったなぁ。