結果
問題 | No.1036 Make One With GCD 2 |
ユーザー | rkyiolklo |
提出日時 | 2020-04-25 00:05:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 738 ms / 2,000 ms |
コード長 | 622 bytes |
コンパイル時間 | 684 ms |
コンパイル使用メモリ | 86,724 KB |
実行使用メモリ | 202,176 KB |
最終ジャッジ日時 | 2023-10-14 19:36:16 |
合計ジャッジ時間 | 20,605 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 707 ms
199,124 KB |
testcase_01 | AC | 331 ms
162,484 KB |
testcase_02 | AC | 453 ms
169,304 KB |
testcase_03 | AC | 132 ms
106,172 KB |
testcase_04 | AC | 169 ms
120,516 KB |
testcase_05 | AC | 69 ms
71,144 KB |
testcase_06 | AC | 67 ms
70,944 KB |
testcase_07 | AC | 211 ms
110,688 KB |
testcase_08 | AC | 191 ms
101,604 KB |
testcase_09 | AC | 465 ms
182,192 KB |
testcase_10 | AC | 440 ms
172,260 KB |
testcase_11 | AC | 458 ms
151,032 KB |
testcase_12 | AC | 449 ms
172,740 KB |
testcase_13 | AC | 636 ms
189,804 KB |
testcase_14 | AC | 634 ms
198,088 KB |
testcase_15 | AC | 618 ms
184,656 KB |
testcase_16 | AC | 617 ms
186,948 KB |
testcase_17 | AC | 622 ms
187,504 KB |
testcase_18 | AC | 87 ms
76,576 KB |
testcase_19 | AC | 93 ms
76,860 KB |
testcase_20 | AC | 95 ms
77,548 KB |
testcase_21 | AC | 96 ms
77,532 KB |
testcase_22 | AC | 597 ms
184,188 KB |
testcase_23 | AC | 474 ms
154,512 KB |
testcase_24 | AC | 623 ms
187,224 KB |
testcase_25 | AC | 571 ms
172,824 KB |
testcase_26 | AC | 592 ms
183,156 KB |
testcase_27 | AC | 70 ms
71,148 KB |
testcase_28 | AC | 71 ms
70,756 KB |
testcase_29 | AC | 69 ms
71,012 KB |
testcase_30 | AC | 70 ms
71,132 KB |
testcase_31 | AC | 71 ms
70,948 KB |
testcase_32 | AC | 71 ms
71,380 KB |
testcase_33 | AC | 68 ms
71,304 KB |
testcase_34 | AC | 70 ms
70,900 KB |
testcase_35 | AC | 69 ms
70,900 KB |
testcase_36 | AC | 67 ms
70,992 KB |
testcase_37 | AC | 69 ms
71,324 KB |
testcase_38 | AC | 719 ms
201,844 KB |
testcase_39 | AC | 588 ms
202,176 KB |
testcase_40 | AC | 482 ms
154,240 KB |
testcase_41 | AC | 675 ms
202,020 KB |
testcase_42 | AC | 649 ms
201,956 KB |
testcase_43 | AC | 714 ms
202,012 KB |
testcase_44 | AC | 738 ms
201,812 KB |
ソースコード
from math import gcd n=int(input()) a=list(map(int,input().split())) sz=1 while sz<n: sz*=2 seg=[0]*(2*sz) for i in range(n): seg[i+sz]=a[i] for i in range(sz-1,0,-1): seg[i]=gcd(seg[2*i],seg[2*i+1]) def query(a,b): if a>=b: return 0 a1=a+sz b1=b+sz ret=0 while a1<b1: if b1&1: b1-=1 ret=gcd(ret,seg[b1]) if a1&1: ret=gcd(ret,seg[a1]) a1+=1 a1>>=1 b1>>=1 return ret ans=0 r=1 for i in range(n): while r<=n: if query(i,r)==1: break r+=1 ans+=(n+1-r) print(ans)