結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-05-09 05:26:11 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,176 ms / 2,000 ms |
コード長 | 522 bytes |
コンパイル時間 | 611 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 73,340 KB |
最終ジャッジ日時 | 2024-09-16 14:20:32 |
合計ジャッジ時間 | 29,249 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
import sysfrom math import gcdimport itertoolsread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesN,*A = map(int, read().split())A = [0] + A + [1]stack = [0]r = 0rv = 0answer = 0for l in range(1, N+1):stack.pop()if not stack:stack = [0] + list(itertools.accumulate(itertools.chain(A[r:l-1:-1]), gcd))rv = 0x = stack[-1]while gcd(x, rv) != 1:r += 1rv = gcd(rv, A[r])answer += N+1-rprint(answer)