Judge System Update Test Contest 202004 D - Calculating GCD

問題原文

atcoder.jp

問題要旨

長さ の正整数列 がある。また、 個の１より大きい整数 が与えられる。
にした場合の以下の問題の答えを求めよ。

• 始め整数 がある。 の順番に、 を で置き換える。
  途中で となる場合はそうなる最小の を、ならない場合は最終的な の値を求めよ。

• 

• 
• 

解法

最後にようやく１になる & 毎回 が変化すると仮定してみる。
すると「最大で何回 が変化するか」は 2 × 2 × 2 × をしていって の制約を超えないギリギリで、これはたったの２９回とかになる。
よって の累積GCDを追っていって、変化する場所を記録すると、そのような についてのみチェックをすることで、愚直に解ける。
ランレングス圧縮っていうらしい！

実装

ありがとう fractions.gcd、こんにちは math.gcd 。

from math import gcd

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

changed_index = [0]
GCD = A[0]
for i, a in enumerate(A[1:], start=1):
    nextGCD = gcd(GCD, a)
    if GCD != nextGCD:
        changed_index.append(i)
    GCD = nextGCD

for s in S:
    X = s
    for ci in changed_index:
        X = gcd(X, A[ci])
        if X == 1:
            print(ci + 1)
            break
    else:
        print(X)

感想

実は制約を良くみると、考えるべきものがぐっと少なくなるパターン、かな？