互いに素(coprime)：AtCoder Beginner Contest 177 E

はじめに

　この記事は, AtCoder Beginner Contest 177 E問題の解法を自分(初学者)の勉強の観点でまとめたものです. 内容は, 公式の解説と参考文献を用いて, 初学者向けにかみ砕いたものです.

問題の理解

　問題文は下記の通り(引用: https://atcoder.jp/contests/abc177/tasks/abc177_e).

　念のため, 最大公約数の定義を順番に確認.

• 定義：約数¹

整数$a$が整数$b$で割りきれるとき, つまり割った余りが$0$のとき, $b$は$a$の約数であるといい, $a$は$b$の倍数であるという.

例：
$12 \div 3 = 4$, したがって$3$は$12$の約数である.

• 定義：公約数, 最大公約数(GCD：greatest common divisor)¹

整数$a$と整数$b$のどちらの約数にもなっている数を公約数といい, 公約数の中で最大のものを最大公約数という.

例：
$8$と$12$の最大公約数を考える. $8$は$1,2,4,8$が約数, $12$は$1,2,3,4,6,12$が約数であるので, 公約数は$1,2,4$となる. したがって, 最大公約数は$4$.

　問題文が理解できたところで, 問題を愚直に解こうとすると, $N$個の整数の任意の対(ペア)に対してGCDを計算して, pairwise coprimeであるのかを確認する方法が考えられます. このとき, 全組合せを考えるだけで, 少なくとも計算量は$O(N^2)$になってしまいます.

解法

　まず, setwise coprimeを確認する方法として, 2つの整数に対する最大公約数を求めるアルゴリズムとして, ユークリッドの互除法を確認. そのあとに, $N$個の整数の最大公約数を求めるアルゴリズムに拡張します.

　次に, pairwise coprimeを確認する方法として, pairwise coprimeであることと同値な条件を考えます. その条件では最大公約数を計算するのではなく素因数分解を利用するので, 素因数分解を工夫して高速に行う方法を確認します.

　最後に, 全体としての流れをまとめます.

1. 最大公約数の求め方と計算量

　最大公約数を求めるアルゴリズムとして, ユークリッドの互除法が知られている. 証明は飛ばしてアルゴリズムの確認をする.

ユークリッドの互除法のアルゴリズム

　参考文献に記載されていたユークリッドの互除法のアルゴリズム¹を簡潔に書き換えたました.

1. 整数$a, b(a > b)$の入力
2. $b=0$ならば5.へ
3. $b\neq 0$ならば, $a$を$b$で割った余り$r$を求める
4. $b, r$を新しい$a, b$として2.から繰り返す
5. $a$を出力して終了

　このアルゴリズムは有限回で収束することが保証されていて, 計算量はラメの定理によって$O(\log b)$となります.

例：
123と45の最大公約数をユークリッドの互除法で求める.

• $a=123, b=45$として$r=33$
• $a=45, b=33$として$r=12$
• $a=33, b=12$として$r=9$
• $a=12, b=9$として$r=3$
• $a=9, b=3$として$r=0$
• $a=3, b=0$で$a=3$を出力して終了

したがって, 123と45の最大公約数は3.

2. 3個以上の整数に対する最大公約数の求め方と計算量

　ユークリッドの互除法のアルゴリズムでは, 入力は2つの整数$a, b$でした. では, $N$個の整数$a_1, ..., a_N$の最大公約数を求めることを考えます. まず, $a_1$と$a_2$の最大公約数を計算すると$g_1$であったとします. 次に, $a_1, a_2, a_3$の最大公約数$g_2$を考えます. 最大公約数はもちろん公約数であるので, 3つの整数に共通する約数であるから, $g_2$は少なくとも$g_1$の約数であるはずです. よって, $g_1$と$a_3$の最大公約数は$g_2$と一致します. したがって, $g_1, g_2=(g_1$と$a_3$の最大公約数$), ..., g_{N-1}=(g_{N-2}$と$a_N$の最大公約数$)$と順番に計算すれば良い分けです.

　計算量は, $A = \max a_i$とすると, 個別の最大公約数を求める計算量は大きくても$O(\log A)$であるから, これを$N-1$回行う必要があるので, $O(N\log A)$であることが分かる.

例：
24, 18, 15の最大公約数を求める.

• 24と18の最大公約数は6
• 6と15の最大公約数は3

したがって, 24, 18, 15の最大公約数は3.

3. 命題の置き換え

　pairwise coprimeについて, 問題文で与えられたまま全ての組合せの最大公約数を計算すると計算量が大きすぎます. これは, 2個ずつ全ての組合せをチェックしていることが原因です. では, $N$個の整数がpairwise coprimeであることと同値な条件を, $N$個の整数に対して同時に満たすべきものとして考えてみます. 任意の組合せの最大公約数が1ということは, どの組合せも共通の素因数(素数かつ約数)を持たないということであり, $N$個の整数全体で考えると, 共通する素因数は0個ということになります.

• 命題

$N$個の整数$A_i$がpairwise coprime $\Leftrightarrow$ 任意の素数$p$に対して, $p$の倍数となる$A_i$は高々1個

証明

($\Rightarrow$)
　どの整数の対(ペア)の組合せでも最大公約数が1であるので, どの整数の対(ペア)の組合せでも共通の素因数を持たない. つまり, 素数$p$について, ある$A_i$の素因数であれば, 他に$p$を素因数にもつ整数$A_j(i\neq j)$は存在しない. このとき, $p$の倍数となる$A_i$は1つ. ある$A_i$の素因数でない素数を$p$とすると, $p$の倍数であるような$A_i$は0個. よって, 任意の素数$p$に対して, $p$の倍数となる$A_i$は高々1個である.

($\Leftarrow$)
　任意の素数$p$に対して, $p$の倍数となる$A_i$は高々1個である. このとき, $N$個の整数の任意の対(ペア)$A_i, A_j(i\neq j)$に対して, ある素数$p$はどちらか一方の素因数であるか, どちらの素因数でもないかである. したがって, 共通の素因数$p$は存在しないので, 最大公約数は1となる.

　よって, 命題を示せた. $\Box$

　この命題の置き換えにより, pairwise coprimeであることを確認するには, 組合せではなく$N$個の整数「個別」に対して素因数を確認して, 素因数の重複が無いことを確認すれば良いことになった.

4. 素因数分解アルゴリズムと計算量

エラトステネスの篩(ふるい)

　エラトステネスの篩とは, 素数を組織的に求める効率的な方法として知られている². アルゴリズムは下記のもので, 整数$A$以下の素数を全て求める計算量は$O(A\log\log A)$である³.

1. $2$以上$A$以下の整数を列挙する
2. $p$を列挙されている整数で最小の素数$2$とし, $2$を保存($p=2$, $2$を素数として保存)
3. $p$の倍数を取り除く(最初は$2$の倍数を取り除く)
4. 残った整数で最小のものは素数であり保存し, 新しい$p$として更新する(最初は$3$を素数として保存し, $p=3$とする)
5. 3.から繰り返す, 列挙した整数が全て取り除かれたら終了

例：
$6$以下の素数を全て求める.

• $2, 3, 4, 5, 6$を列挙する(列挙：$\{2, 3, 4, 5, 6\}$)
• $p=2$, $2$を素数として保存(列挙：$\{2, 3, 4, 5, 6\}$, 素数：$\{2\}$)
• $p=2$の倍数を取り除く(列挙：$\{3, 5\}$, 素数：$\{2\}$)
• 残った整数で最小の$3$を素数として保存し$p=3$とする(列挙：$\{3, 5\}$, 素数：$\{2, 3\}$)
• $p=3$の倍数を取り除く(列挙：$\{5\}$, 素数：$\{2, 3\}$)
• 残った整数で最小の$5$を素数として保存し$p=5$とする(列挙：$\{5\}$, 素数：$\{2, 3, 5\}$)
• $p=5$の倍数を取り除く(列挙：$\{\}$, 素数：$\{2, 3, 5\}$)
• 列挙した整数が全て取り除かれたので終了

したがって, $6$以下の素数として$\{2, 3, 5\}$を求めることができた.

工夫した素因数分解アルゴリズム

　先ほどのエラトステネスの篩によってアルゴリズム中において削除した整数$x(\leq A)$を, 削除の要因となった素数$p$と$D[x] = p$の様に紐づけて取得しておきます. このとき, $D[x]$は$x$の最小の素因数となります. これらを利用して, 次のように整数$A$を素因数分解します.

1. $D[A]$で$A$を割った商を$q$とする, $D[A]$を素因数として保存(例：$D[8]=2$)
2. $q$を新しい$A$とする
3. $q=1$になるまで1.から繰り返す

　このアルゴリズムは一つの整数$A$に対して, 重複も含めた$A$の素因数の個数が$O(\log A)$であることから, 素因数の個数だけ繰り返し計算するので, この計算量は$O(\log A)$となる.

例：
$12$を素因数分解する. このとき,
$D[2]=D[4]=D[6]=D[8]=D[10]=D[12]=2$,
$D[3]=D[9]=3$,
$D[5]=5, D[7]=7, D[11]=11$は事前に取得しているものとする.

• $D[12]=2$で$12$を割った商は$q=6$(保存：$\{2\}$)
• $A=6$とする
• $D[6]=2$で$6$を割った商は$q=3$(保存：$\{2, 2\}$)
• $A=3$とする
• $D[3]=3$で$3$を割った商は$q=1$(保存：$\{2, 2, 3\}$)
• $q=1$となったので, 終了

したがって, $12=2^2\times 3^1$と素因数分解できた.

5. まとめ

　以上より, 大元の問題を解く手順は下記のようになります.

1. 入力は$N$個の整数で, $A_1, ..., A_N$
2. $A = \max A_i$を計算, 計算量は$O(N)$
3. 入力された$N$個の整数についてsetwise coprimeであるのかを確認, 計算量は$O(N\log A)$
4. setwise coprimeでなければpairwise coprimeでもないのでnot coprimeと出力して終了
5. setwise coprimeであればpairwise coprimeであるのかを確認していく
6. エラトステネスの篩により$D[x](2\leq x\leq A)$を作成する, 計算量は$O(A\log\log A)$
7. $D[x]$を用いて$A_1$から$A_N$まで順番に素因数分解を行い, $A_i$をまたいで素因数に重複があるか確認, 計算量は$O(N\log A)$
8. 素因数に重複があればsetwise coprime, 重複が無ければpairwise coprimeを出力する

　このアルゴリズム全体での計算量は
$$O(A\log\log A + N\log A).$$

実装

　Pythonで実装する. Atcoder上での実行時間は527 msで, 無事ACされました.

from math import gcd

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check_fun(A_list, D, A_max):
    p_count = [0] * (A_max + 1)
    for A in A_list:
        temp = A
        d = 0
        while temp != 1:
            if p_count[D[temp]] == 1 and d != D[temp]:
                return 0
            p_count[D[temp]] = 1
            d = D[temp]
            temp = temp // D[temp]
    return 1

## 標準入力
N = int(input())
A_list = list(map(int, input().split(" ")))

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check_fun(A_list, D, A_max) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

感想

　解法を調べていく過程で, 昔勉強した数学周りの知識を色々と忘れていることに気づきました. やっぱり, なるべく数学に取り組む時間を作って, 抜けていくのを防がないといけないなと改めて思いました.
　プロコンに関しては, 本当に初心者で計算量を減らすアイデアは後追いでの理解で精いっぱいの感じです. 経験を積んで自分で導けるようにしていきたいです.

1. 木田祐司：初等整数論, 2003年, 朝倉書店 ↩ ↩² ↩³

2. 新妻弘, 木村哲三：群・環・体入門, 1999年, 共立出版 ↩

3. 秋葉拓哉, 岩田陽一, 北川宜稔：プログラミングコンテストチャレンジブック 第2版, 2012年, マイナビ出版 ↩