ABC177 - EをRubyで解く

# はじめに
[AtCoder Beginner Contest 177](https://atcoder.jp/contests/abc177)の[E問題](https://atcoder.jp/contests/abc177/tasks/abc177_e)について細かく解説を書く機会があり、思いのほか出来が良かったので記事としてまとめようと思う。

# 考察
[問題](https://atcoder.jp/contests/abc177/tasks/abc177_e)より、焦点を以下の順番で三つに分割できる。

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

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

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

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

```ruby
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)なので、考察する余地はない。

```ruby
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 モジュール)](https://qiita.com/norioc/items/5c270ad6ff5d22d1efd0)

これなら楽々解けそうだ。
提出！
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299962/96fb3637-2ee3-b5b5-8ae0-c6c334c31140.png)


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

## osa_k法
[エラトステネスのふるいと高速素因数分解](https://blog.manuel1024.com/archives/79)を見てもらうのが一番早いのだが、ここでも自分なりに解説していく。

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となる。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299962/73e4be64-f038-8919-bacf-f300ead69f2d.png)

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299962/17fb78c4-307f-87ce-85e0-525921026592.png)

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

### 本処理

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299962/c776800c-ea96-5515-09dd-8be7832632f6.png)

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299962/71d367cb-595c-4482-a635-c19c3687a5a2.png)

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

# 実装

```ruby
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

# おわりに
[エラトステネスのふるいと高速素因数分解](https://blog.manuel1024.com/archives/79)のおかげでAC出来た。ここに感謝の意を表したい。