結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-05-02 05:07:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 605 ms / 2,000 ms |
コード長 | 1,538 bytes |
コンパイル時間 | 257 ms |
コンパイル使用メモリ | 82,200 KB |
実行使用メモリ | 259,780 KB |
最終ジャッジ日時 | 2024-09-16 14:20:49 |
合計ジャッジ時間 | 15,901 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
from math import gcdclass SparseTable:"""区間取得クエリをO(1)で答えるデータ構造をO(NlogN)で構築するquery(l, r): 区間[l, r)に対するクエリに答える"""def __init__(self, array):n = len(array)self.row_size = n.bit_length()# log_tableを構築する# log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]self.log_tbl = [0] * (n + 1)for i in range(2, n + 1):self.log_tbl[i] = self.log_tbl[i // 2] + 1# sparse_tableを構築するself.sp_tbl = [0] * (n * self.row_size)for i in range(n):self.sp_tbl[i] = array[i]for row in range(1, self.row_size):for i in range(n - (1 << row) + 1):self.sp_tbl[row * n + i] = \gcd(self.sp_tbl[(row - 1) * n + i],self.sp_tbl[(row - 1) * n + i + (1 << row - 1)])# def _merge(self, num1, num2):# """冪等律と結合律を満たす演算を行う"""# return gcd(num1, num2)def query(self, l, r):"""区間[l, r)に対するクエリに答える"""row = self.log_tbl[r - l]return gcd(self.sp_tbl[row * n + l],self.sp_tbl[row * n + r - (1 << row)])import sysinput = sys.stdin.readlinen = int(input())a = list(map(int, input().split()))sp = SparseTable(a)r = 1ans = 0for l in range(n):r = max(l + 1, r)while r <= n and sp.query(l, r) != 1:r += 1ans += n - r + 1print(ans)