E - Coprime

[hxrxchang]

https://atcoder.jp/contests/abc177/tasks/abc177_e

問題概要

要素数Nの数列Aがある。

• 1~Nのうち2つの数字の組である (i, j) のすべてに於いて、GCD(A[i], A[j]) == 1であれば、pairwise coprime を出力せよ
• ↑ではなく、GCD(A[1] ... A[N]) == 1 であれば、setwise coprime を出力せよ
• 上記どちらでもなければ、not coprime と出力せよ

解き方

setwise coprime であるかどうかは、最大公約数の取得は O(logN) なので、全要素確かめてもO(N * logN) で間に合う。 pairwise coprime であるかどうかは、あらかじめ10 6以下の素数を列挙しておき、各素数の倍数がAの中に何回出現するか を求め、それが2回以上あることが分かった段階で、pairwise coprime でないことがわかる。 この部分の計算量は 10 6以下の素数の数 (78498) の2乗になりそうだが、実際は数が大きくなると繰り返しが少なくなるので、N * logN になる。

func solve() {
    MAX := pow(10, 6) + 1
    getInt()
    a := getInts()

    num := make([]int, MAX)
    for _, v := range a {
        num[v]++
    }

    isPrime := make([]bool, MAX)
    pn := primeNumbers(MAX)
    for _, v := range pn {
        isPrime[v] = true
    }

    coprime := true
    for _, v := range pn {
        sum := 0
        for i := v; i < MAX; i += v {
            sum += num[i]
            if sum > 1 {
                coprime = false
                break
            }
        }
    }

    if coprime {
        fmt.Println("pairwise coprime")
        return
    }

    g := 0
    for _, v := range a {
        g = gcd(g, v)
    }

    if g == 1 {
        fmt.Println("setwise coprime")
        return
    }

    fmt.Println("not coprime")
}

https://atcoder.jp/contests/abc177/submissions/53957813