結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
|
提出日時 | 2024-01-24 03:30:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,976 ms / 2,000 ms |
コード長 | 2,480 bytes |
コンパイル時間 | 288 ms |
コンパイル使用メモリ | 82,456 KB |
実行使用メモリ | 336,836 KB |
最終ジャッジ日時 | 2024-09-28 06:59:33 |
合計ジャッジ時間 | 45,648 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
## https://yukicoder.me/problems/no/1036def calc_gcd(A, B):"""正の整数A, Bの最大公約数を計算する"""a = max(A, B)b = min(A, B)while a % b > 0:c = a % ba = bb = creturn bclass SparseTable:def __init__(self, A):self.N = len(A)k = 0while (1 << k) < self.N:k += 1self.max_k = kself.table = [[] for _ in range(self.N)]for k in range(self.max_k + 1):for i in range(self.N):if k == 0:self.table[i].append(A[i])else:if i + (1 << k) - 1 < self.N:if len(self.table[i]) < k:continueif len(self.table[i + (1 << (k - 1))]) < k:continuea = self.table[i][k - 1]b = self.table[i + (1 << (k - 1))][k - 1]self.table[i].append(calc_gcd(a, b))def query(self, l, r):length = r - l + 1if length == 1:return self.table[l][0]k = 0while (1 << k) < length:k += 1k -= 1a = self.table[l][k]b = self.table[r - ((1 << k) - 1)][k]return calc_gcd(a, b)def main():N = int(input())A = list(map(int, input().split()))st = SparseTable(A)answer = 0left = 0right = 0a = A[0]while left < N and a == 1:answer += N - leftleft += 1right += 1if left < N:a = A[left]else:a = 0while left < N:while right < N - 1 and calc_gcd(a, A[right + 1]) > 1:a = calc_gcd(a, A[right + 1])right += 1if right < N - 1:answer += N - (right + 1)if left < right:left += 1a = st.query(left, right)else:left += 1right += 1a = A[left]while left < N and a == 1:answer += N - leftleft += 1right += 1if left < N:a = A[left]else:a = 0else:breakprint(answer)if __name__ == "__main__":main()