はじめに

AtCoder Beginner Contest 177のE問題について細かく解説を書く機会があり、思いのほか出来が良かったので記事としてまとめようと思う。

考察

問題より、焦点を以下の順番で三つに分割できる。

『全ての1 ≦ i < j ≦ N について、GCD(A_i, A_j) = 1』が成り立つ
『GCD(A_1 …… A_N) = 1』が成り立つ
いずれも成り立たない

次より、これら三つをより細かく見ていく。

1.『全ての1 ≦ i < j ≦ N について、GCD(A_i, A_j) = 1』が成り立つ

全ての場合を愚直に求める。

N.times do |i|
  N.times do |j|
    if A[i].gcd(A[j]) != 1 then
      is_pairwise_coprime = false
    end
  end
end

制約より、$2≤N≤10^6$ なので最大が $O(10^{12})$ となって実行時間制限2secに間に合わない。

ここでいずれの組み合わせの最大公約数が1となる点に注目する。
これはどの整数の組み合わせ $(A_i, A_j)$ も互いに素であると言い換えられる。

よって、N個の整数全てを素因数分解をして、同じ素因数が出てこなければこれが成り立ち、pairwise coprimeを出力する。

2.『GCD(A_1 …… A_N) = 1』が成り立つ

これは愚直にまわしてもO(N)なので、考察する余地はない。

res = a[0]
a.each do |elm|
  res = res.gcd(elm)
end

1が成り立たないとき、かつ、res == 1のとき、setwise coprimeを出力すればいい。
そして、3.いずれも成り立たないとき、not coprimeを出力する。

これより、1が考察の主となる。

素因数分解

Rubyにはprimeモジュールがあり、これのPrime.prime_divisionより素因数分解ができる。
参考：Rubyで素数で遊ぶ(prime モジュール)

これなら楽々解けそうだ。
提出！

間に合わない。ではどうするか。

osa_k法

エラトステネスのふるいと高速素因数分解を見てもらうのが一番早いのだが、ここでも自分なりに解説していく。

N(今回は $A_{max}$ )以下の正の整数を素因数分解するアルゴリズムであり、前処理($O(log log N)$)の後、ある数Mの素因数を求める本処理($O(log M)$)を行う。
計算量は $O(log log N + log M)$より、 $O(log M)$。
今回の最大値 $A_{max} = 10^6$ より $O(log 10^6) = O(10)$ 程度になる。
従って、N個全ての整数全ての素因数を求める計算量は $O(N log A_{max}) = O(10^7)$ 程度となり、十分間に合う。

要約すると、

正の整数を素因数分解する
最小の素因数を求める前処理を行う
前処理した結果を用いて素因数分解を高速に行う

アルゴリズムである

前処理

$N = A_{max}$ 以下の整数(1~N)について、最小の素因数min_factorを求める。
エラトステネスの篩の応用で、i(= 2 ~ $\sqrt{N}$)の倍数kを順にみて、iがkに入っている値より小さければiを入れる。

例：
素因数分解したい値の最大値N=16を例に挙げる。
$\sqrt{16} = 4$なので、iの範囲は2~4となる。

iを順番に見て行って最小の素因数を格納した配列min_factorをつくる。

最後の部分が配列min_factorとなる。

本処理

以下のフローチャートを参考にされたい。

resultに素因数分解した結果が格納される。
同じ素数が複数格納されるので、素因数のみ欲しい場合はuniqやsetを使う。

上記の例を以上のフローにあてはめると下図の通りになる。

これでACするコードを書けそうだ。

実装

class Osa_k
    # @parm {number} n - 素因数分解したい値の中での最大値
    def initialize(n)
        @min_factor = [*0..n]
        i = 2
        while i * i <= n do
            if @min_factor[i] == i then
                j = 2
                while i * j <= n do
                    @min_factor[i*j] = i if @min_factor[i*j] > i
                    j += 1
                end
            end
            i += 1
        end
    end

    # @parm {number} m - 素因数分解したい値
    # @return {array} res - mの素因数群
    def factor(m)
        res = []
        tmp = m
        while tmp > 1 do
            res << @min_factor[tmp]
            tmp /= @min_factor[tmp]
        end
        return res.uniq
    end
end

MAX = 10 ** 6 + 10 # 最大値が10^6なので
n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)
osa_k = Osa_k.new(MAX)
res = a[0]
h = Hash.new(0) # 連想配列を用いて素因数が既出かどうかを管理
is_pairwise_coprime = true # 1つ目の条件を満たしているかどうか
n.times do |i|
    # 1つ目の条件が満たされないと分かった時点でやる必要はない
    if is_pairwise_coprime then
        osa_k.factor(a[i]).each do |num, cnt|
            if h.has_key?(num) then
                is_pairwise_coprime = false
                break
            end
            h[num] += 1
        end
    end
    res = res.gcd(a[i]) # 2つ目の条件を確認
end

if is_pairwise_coprime then
    puts "pairwise coprime"
elsif res == 1 then
    puts "setwise coprime"
else
    puts "not coprime"
end

提出結果：https://atcoder.jp/contests/abc177/submissions/16583524

おわりに

エラトステネスのふるいと高速素因数分解のおかげでAC出来た。ここに感謝の意を表したい。

ABC177 - EをRubyで解く