結果

問題 No.1036 Make One With GCD 2
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-01-24 03:26:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,599 bytes
コンパイル時間 288 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 337,252 KB
最終ジャッジ日時 2024-09-28 06:58:46
合計ジャッジ時間 50,431 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 39 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

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

## https://yukicoder.me/problems/no/1036
def calc_gcd(A, B):
"""
A, B
"""
a = max(A, B)
b = min(A, B)
while a % b > 0:
c = a % b
a = b
b = c
return b
class SparseTable:
def __init__(self, A):
self.N = len(A)
k = 0
while (1 << k) < self.N:
k += 1
self.max_k = k
self.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:
continue
if len(self.table[i + (1 << (k - 1))]) < k:
continue
a = 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 + 1
if length == 1:
return self.table[l][0]
k = 0
while (1 << k) < length:
k += 1
k -= 1
a = 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 = 0
left = 0
right = 0
a = A[0]
while left < N and a == 1:
answer += N - left
left += 1
right += 1
if left < N:
a = A[left]
else:
a = 0
while left < N:
while right < N - 1 and calc_gcd(a, A[right + 1]) > 1:
a = calc_gcd(a, A[right + 1])
right += 1
if right < N - 1:
answer += N - (right + 1)
if left < right:
left += 1
a = st.query(left, right)
else:
left += 1
right += 1
a = A[left]
while left < N and a == 1:
answer += N - left
left += 1
right += 1
if left < N:
a = A[left]
else:
a = 0
else:
if left < right:
left += 1
a = st.query(left, right)
else:
break
print(answer)
if __name__ == "__main__":
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0