Atcoder ABC125 C - GCD on Blackboard 別解集 - Qiita

C問題なのに脅威の水色 ちょっと捻ってるだけでネタが分かれば解けるヤツ 累積GCD これが正攻法 左から順番にgcdを取っていって記録していく 右からも同様に あとで各一点に対して記録した左側gcdと右側gcdで仲良しさせる def euclid(a,b): a,b=max(a,b),min(a,b) if a%b==0: return b else: a,b=b,a%b return euclid(a,b) N=int(input()) A=list(map(int,input().split())) org_A=A[:] #左から最大公約数作る右もね A=A[::-1] l=[A.pop(-1)] while A: l.append(euclid(l[-1],A.pop(-1))) A=org_A r=[A.pop(-1)] while A: r.append(euclid(r[-1]