結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
package mainimport ("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 []intoffset int}func newSegmentTree(n int) segmentTree {var result segmentTreet := 1for t < n {t *= 2}result.offset = t - 1result.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 + indexst.data[i] = valuefor i >= 1 {i = (i - 1) / 2st.data[i] = gcd(st.data[i*2+1], st.data[i*2+2])}}func (st segmentTree) query(start, stop int) int {result := 0l := start + st.offsetr := stop + st.offsetfor 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 / 2r = (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 := 0j := 1for 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...)}