ABC125_C --GCD on Blackboard [Notes solved in Python]

・ [ABC125_C --GCD on Blackboard] (https://atcoder.jp/contests/abc125/tasks/abc125_c)

N integers A1, A2, .... An are entered. The question of what is the greatest common divisor of N integers when one of them is replaced with an arbitrary integer.

Well, I don't know, but the result of crushing the numbers one by one and turning gcd around to solve it. ・ ....

Bad solution

As a result of implementing it without thinking about anything, the amount of calculation became tremendous by turning gcd from end to end every time I changed the number to be crushed, and I wrote a code that made me crazy and died.

    import sys
    input = sys.stdin.readline
     
    import numpy as np
    import fractions
    from functools import reduce
     
    from copy import deepcopy
     
     
    def gcd_list(nums):
        return reduce(fractions.gcd, nums)
     
    def main():
        N = int(input())
        A = np.array(sorted(list(map(int, input().split()))))
     
        bools = np.ones(N, dtype=bool)
     
        ans = 0
        vals = []
        for i in range(N):
            A_cop = deepcopy(A)
            bl_cop = deepcopy(bools)
     
            fal = [i]
            bl_cop[fal] = False
     
            vals.append(gcd_list(A_cop[bl_cop]))
     
        print(max(vals))
     
    main()

＞ Sudden TLE <

Good solution

Set the number to be crushed as Ai, and find the greatest common divisor for each of the interval [A0, Ai) and the interval (Ai, An]. Furthermore, by finding the greatest common divisor of those two numbers, the greatest common divisor that can be taken when Ai is crushed can be found, so it is okay if the greatest common divisor (Gestaltzerfall feeling) is taken out after performing this operation on all integers.

If you use this method, you can carry over the value used when calculating the greatest common divisor of the previous Ai when finding the greatest common divisor of the two sections that sandwich Ai, so from the end That you don't have to calculate all the way to the end

It seems to be called cumulative GCD (I haven't even hit the cumulative sum yet)

    import sys
    input = sys.stdin.readline
    import fractions
    
    
    def main():
        N = int(input())
        A = list(map(int, input().split()))
    
        L_gcds = [0] * N
        L_gcd_tmp = L_gcds[0]
        for i in range(1, N):
            L_gcd_tmp = fractions.gcd(L_gcd_tmp, A[i-1])
            L_gcds[i] = L_gcd_tmp
    
        R_gcds = [0] * N
        R_gcd_tmp = R_gcds[0]
        for j in range(1, N):
            R_gcd_tmp = fractions.gcd(R_gcd_tmp, A[N-j])
            R_gcds[j] = R_gcd_tmp
        R_gcds.reverse()
    
        LR_gcds = [0] * N
        for k in range(0, N):
            LR_gcds[k] = fractions.gcd(L_gcds[k], R_gcds[k])
    
        print(max(LR_gcds))
    
    main()

Learn

――Let's see the restrictions properly ――Let's think about the amount of calculation before implementing it.