結果

問題 No.1036 Make One With GCD 2
ユーザー c-yan
提出日時 2020-04-24 22:23:20
言語 Go
(1.23.4)
結果
AC  
実行時間 824 ms / 2,000 ms
コード長 2,253 bytes
コンパイル時間 15,924 ms
コンパイル使用メモリ 240,712 KB
実行使用メモリ 15,968 KB
最終ジャッジ日時 2024-09-16 13:19:55
合計ジャッジ時間 28,114 ms
ジャッジサーバーID
(参考情報)
judge4 / judge6
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
func gcd(a, b int) int {
if a < b {
a, b = b, a
}
for b > 0 {
a, b = b, a%b
}
return a
}
type segmentTree struct {
data []int
offset int
}
func newSegmentTree(n int) segmentTree {
var result segmentTree
t := 1
for t < n {
t *= 2
}
result.offset = t - 1
result.data = make([]int, 2*t-1)
return result
}
func (st segmentTree) updateAll(a []int) {
for i, v := range a {
st.data[st.offset+i] = v
}
for i := st.offset - 1; i > -1; i-- {
st.data[i] = gcd(st.data[i*2+1], st.data[i*2+2])
}
}
func (st segmentTree) update(index, value int) {
i := st.offset + index
st.data[i] = value
for i >= 1 {
i = (i - 1) / 2
st.data[i] = gcd(st.data[i*2+1], st.data[i*2+2])
}
}
func (st segmentTree) query(start, stop int) int {
result := 0
l := start + st.offset
r := stop + st.offset
for l < r {
if l&1 == 0 {
result = gcd(result, st.data[l])
}
if r&1 == 0 {
result = gcd(result, st.data[r-1])
}
l = l / 2
r = (r - 1) / 2
}
return result
}
func main() {
defer flush()
N := readInt()
A := make([]int, N)
for i := 0; i < N; i++ {
A[i] = readInt()
}
st := newSegmentTree(N)
st.updateAll(A)
result := 0
j := 1
for i := 0; i < N; i++ {
v := st.query(i, j)
for v != 1 && j < N {
v = gcd(v, A[j])
j++
}
if v != 1 {
break
}
result += N - j + 1
}
println(result)
}
const (
ioBufferSize = 1 * 1024 * 1024 // 1 MB
)
var stdinScanner = func() *bufio.Scanner {
result := bufio.NewScanner(os.Stdin)
result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
result.Split(bufio.ScanWords)
return result
}()
func readString() string {
stdinScanner.Scan()
return stdinScanner.Text()
}
func readInt() int {
result, err := strconv.Atoi(readString())
if err != nil {
panic(err)
}
return result
}
func readInts(n int) []int {
result := make([]int, n)
for i := 0; i < n; i++ {
result[i] = readInt()
}
return result
}
var stdoutWriter = bufio.NewWriter(os.Stdout)
func flush() {
stdoutWriter.Flush()
}
func printf(f string, args ...interface{}) (int, error) {
return fmt.Fprintf(stdoutWriter, f, args...)
}
func println(args ...interface{}) (int, error) {
return fmt.Fprintln(stdoutWriter, args...)
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0