結果

問題 No.1036 Make One With GCD 2
ユーザー rlangevinrlangevin
提出日時 2024-01-15 12:12:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,400 ms / 2,000 ms
コード長 3,570 bytes
コンパイル時間 378 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 200,028 KB
最終ジャッジ日時 2024-09-28 02:15:18
合計ジャッジ時間 25,219 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class SegmentTree:
def __init__(self,
n,
identity_e,
combine_f,
):
self._n = n
self._size = 1
while self._size < self._n:
self._size <<= 1
self._identity_e = identity_e
self._combine_f = combine_f
self._node = [self._identity_e] * (2 * self._size)
def build(self, array):
assert len(array) == self._n
for index, value in enumerate(array, start=self._size):
self._node[index] = value
for index in range(self._size - 1, 0, -1):
self._node[index] = self._combine_f(
self._node[index << 1 | 0],
self._node[index << 1 | 1]
)
def update(self, index, value):
i = self._size + index
self._node[i] = value
while i > 1:
i >>= 1
self._node[i] = self._combine_f(
self._node[i << 1 | 0],
self._node[i << 1 | 1]
)
def fold(self, L, R):
L += self._size
R += self._size
value_L = self._identity_e
value_R = self._identity_e
while L < R:
if L & 1:
value_L = self._combine_f(value_L, self._node[L])
L += 1
if R & 1:
R -= 1
value_R = self._combine_f(self._node[R], value_R)
L >>= 1
R >>= 1
return self._combine_f(value_L, value_R)
def get(self, p):
return self._node[p + self._size]
def max_right(self, l, f):
assert 0 <= l <= self._n
assert f(self._identity_e)
if l == self._n:
return self._n
l += self._size
sm = self._identity_e
while True:
while l % 2 == 0:
l >>= 1
if not f(self._combine_f(sm, self._node[l])):
while l < self._size:
l <<= 1
if f(self._combine_f(sm, self._node[l])):
sm = self._combine_f(sm, self._node[l])
l += 1
return l - self._size
sm = self._combine_f(sm, self._node[l])
l += 1
if l & -l == l:
break
return self._n
def min_left(self, r, f):
assert 0 <= r <= self._n
assert f(self._identity_e)
if r == 0:
return 0
r += self._size
sm = self._identity_e
while True:
r -= 1
while r > 1 and r % 2:
r >>= 1
if not f(self._combine_f(self._node[r], sm)):
while r < self._size:
r = 2 * r + 1
if f(self._combine_f(self._node[r], sm)):
sm = self._combine_f(self._node[r], sm)
r -= 1
return r + 1 - self._size
sm = self._combine_f(self._node[r], sm)
if r & -r == r:
break
return 0
from math import gcd
N = int(input())
A = list(map(int, input().split()))
T = SegmentTree(N, 0, gcd)
T.build(A)
ans = N * (N + 1) // 2
def f(x):
return x != 1
for i in range(N):
ans -= i+1 - T.min_left(i+1, f)
# if T.fold(i, N) != 1:
# ans -= N - i
# continue
# yes = i
# no = N
# while no - yes != 1:
# mid = (yes + no) // 2
# if T.fold(i, mid) != 1:
# yes = mid
# else:
# no = mid
# ans -= yes - i
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0