AtCoder ABC125 C - GCD on Blackboard (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。先週のコンテストはC問題もD問題も難しかったので過去問（リベンジ）回です。

問題

累積GCDなるフレーズが一時トレンド入りしたりしました。累積和と微妙に扱いが異なる点に注意が必要です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func GCD(a, b int) int {
    if a < b {
        a, b = b, a
    }
    if a%b == 0 {
        return b
    }
    return GCD(b, a%b)
}

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n := nextInt()
    aArray := make([]int, n)
    for i := range aArray {
        aArray[i] = nextInt()
    }

    leftCumGcd, rightCumGcd := make([]int, n), make([]int, n)
    leftCumGcd[0] = aArray[0]
    for i := 1; i < n; i++ {
        leftCumGcd[i] = GCD(leftCumGcd[i-1], aArray[i])
    }
    rightCumGcd[n-1] = aArray[n-1]
    for i := n - 2; i >= 0; i-- {
        rightCumGcd[i] = GCD(rightCumGcd[i+1], aArray[i])
    }

    ans := 1
    for i := 0; i < n; i++ {
        switch {
        case i == 0:
            ans = maxInt(ans, rightCumGcd[i+1])
        case i == n-1:
            ans = maxInt(ans, leftCumGcd[i-1])
        default:
            ans = maxInt(ans, GCD(leftCumGcd[i-1], rightCumGcd[i+1]))
        }
    }
    fmt.Println(ans)
}

$N\geq2$ より、選んだ整数を他のいずれかの整数と同じ値に書き換えることができるため、整数を書き換える操作はその整数を除外する操作に置き換えることができます。つまり各整数についてそれを除外した残りの値の最大公約数を求めて最大値を取ればよいです。

ここで最大公約数の性質について考えてみると、

入力に2つの整数をとり、出力として1つの整数を返す。
結合法則（と交換法則）が成り立つ。

という面から加算や乗算と同じような性質を持つことがわかります。ここから累積最大公約数（累積GCD）を考えるとよさそうに思えます。

ただし、累積和（加算）に対する減算、累積積（乗算）に対する除算といったものが累積GCDには存在しません。つまり単純な（一方向の）累積GCDからは部分GCDを求めることができません。

実は両端から（両方向に）累積GCDを計算すると上手くいきます。どういうことかというと、1つを除いた残りの整数について最大公約数を求めればよいため、両端からの累積GCDに対して最大公約数を計算するという手法を使うことができます。

雑記

今回は雑記のネタがないです。