結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:09:38 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,938 ms / 2,000 ms |
コード長 | 1,752 bytes |
コンパイル時間 | 121 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 73,576 KB |
最終ジャッジ日時 | 2024-11-07 02:31:48 |
合計ジャッジ時間 | 42,162 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
"""sliding window aggrigationモノイドのqueueを管理するfold_all: すべてをたたみこむpopleftappend"""from itertools import accumulatefrom collections import dequeclass SWAG:def __init__(self, operator_M, e_M):self.op_M = operator_Mself.op_rev = lambda x,y: self.op_M(y,x)self.e_M = e_Mself.q = deque([])self.accL = []self.accR = e_Mself.L = self.R = 0def build(self,lst):self.q = deque(lst)self.L = len(lst)self.accL = list(accumulate(reversed(lst),self.op_rev))def __len__(self):return self.L + self.Rdef fold_all(self):if self.L: return self.op_M(self.accL[-1],self.accR)else: return self.accRdef append(self,x):self.q.append(x)self.accR = self.op_M(self.accR,x)self.R += 1def popleft(self):if self.L:self.accL.pop()self.L -= 1return self.q.popleft()elif self.R:v = self.q.popleft()self.L,self.R = self.R-1,0self.accL = list(accumulate(reversed(self.q),self.op_rev))self.accR = self.e_Mreturn velse:assert 0def __repr__(self):return "{}\naccL:{}, accR:{}".format(self.q,self.accL,self.accR)# coding: utf-8# Your code here!import sysreadline = sys.stdin.readlineread = sys.stdin.readn,*a = [int(i) for i in read().split()]from math import gcdq = SWAG(gcd,0)ans = r = 0for l,al in enumerate(a):if len(q): q.popleft()else: r = lwhile r<n and gcd(q.fold_all(),a[r]) != 1:q.append(a[r])r += 1ans += n-rprint(ans)