結果

問題 No.1036 Make One With GCD 2
コンテスト
ユーザー maspy
提出日時 2020-04-25 16:35:09
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 679 bytes
コンパイル時間 113 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 151,980 KB
最終ジャッジ日時 2024-11-07 21:16:04
合計ジャッジ時間 47,892 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 37 TLE * 3 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
N = int(readline())
A = np.array(read().split() + [1], np.int64)

# sparse table
sp = [np.ones(N + 1, np.int64) for _ in range(20)]
sp[0] = A
for n in range(1, 20):
    dx = 1 << (n - 1)
    sp[n][:-dx] = np.gcd(sp[n - 1][:-dx], sp[n - 1][dx:])

# [L,R) の gcd は 1 ではない。のうちで R を 最大化
L = np.arange(N)
R = L.copy()
G = np.zeros(N, np.int64)
for n in range(19, -1, -1):
    G1 = np.gcd(G, sp[n][R])
    go = G1 != 1
    R[go] += 1 << n
    G[go] = G1[go]

ng = (R - L).sum()
total = N * (N + 1) // 2
print(total - ng)
0