2019-10-03

AtCoder ABC 142 D - Disjoint Set of Common Divisors (緑色, 400 点)

すごく楽しくて教育的な整数問題

問題へのリンク

問題概要

2 つの正の整数 $A, B$ が与えられる。 $A, B$ の公約数から何個か整数を選ぶことを考える。

選んだ整数からどの 2 つをとっても、それらが互いに素になるようにしたい。

選べる個数の最大値を求めよ。

制約

$1 \le A, B \le 10^{12}$

考えたこと

まずそもそも、どうすれば $A, B$ の公約数を列挙できるのかを考えてみたい。実は

$A, B$ の公約数を列挙したもの
$A, B$ の最大公約数を $G$ として $G$ の約数を列挙したもの

は完璧に一致するのだ。ちょっとその感触をつかんでみたい。

たとえば 36 と 48 の公約数は

1, 2, 3, 4, 6, 12

である。これはちょうど 36 と 48 の最大公約数である 12 の約数になっている！！！この事実は直感的には明らかだし、実は高校数学で無意識にそう思ってた方も多いと思う。(一応一番下で証明を載せた)。

なお、「公約数は最大公約数の約数」を知らなくても解く方法もある (それも下に載せた)。

シンプルな問題に

以上から問題は $A, B$ の最大公約数を $G$ として

$G$ の約数から何個か選びたい
選んだ整数たちのどの 2 つをとっても互いに素になるようにしたい
最大で何個選べるか

という問題に帰着された。これは一見難しく見えるが、素因数分解のことを知っていれば実はそんなに難しくない。なお素因数分解は $O(\sqrt{G})$ でできるのだが、そのやり方は、たとえば蟻本や螺旋本に載っている。

さて、たとえば $G = 60$ としてみよう。 $60 = 2^{2} \times 3 \times 5^{2}$ である。そうすると $60$ の約数は以下の 12 個になる:

$1$
$2$
$2^{2} = 4$
$3$
$5$
$2 \times 3 = 6$
$2^{2} \times 3 = 12$
$2 \times 5 = 10$
$2^{2} \times 5 = 20$
$3 \times 5 = 15$
$2 \times 3 \times 5 = 30$
$2^{2} \times 3 \times 5 = 60$

つまり、 $2^{a} \times 3^{b} \times 5^{c}$ ( $a = 0, 1, 2$ 、 $b = 0, 1$ 、 $c = 0, 1$ ) が約数の全体になる。

そして互いに素ということは「共通の素因数を持たない」ということ。つまり

$2 \times 3^{2} = 18$
$5^{3} = 125$

は互いに素だが

$2 \times 3^{2} = 12$
$3 \times 5 = 15$

は「3」が被っているので互いに素ではない。

では、 $60 = 2^{2} \times 3 \times 5$ の約数から互いに素になるように、なるべく多く選ぼうと思うと

と選べば良さそうという直感がはたらく。まず $1$ は絶対入れる。これはいかなる整数とも互いに素なので入れて損はない。1 以外は「素因数分解に出てくる素因数」を並べると良さそう。

一応、これを超えることはできないことをちゃんと証明しておきたい。60 の約数に含まれる素因数は 2, 3, 5 以外にはありえない。よって、1 を除くと、約数を 1 個選ぶたびに、1 個以上の素因数を潰すことになる。たとえば $4$ を選ぶと素因数は 2 のみだから 2 を潰す (今後 2 を素因数に含む奴は二度と選べなくなる)。 $6$ を選ぶと素因数は 2, 3 だから 2 と 3 を潰すことになる。

そうすると、1 を除くと、たかだか 3 個までしか選べない！！！

一般化すると、 $G$ を素因数分解に登場する素因数が $p_1, p_2, \dots, p_n$ の $n$ 個があったとすると、答えは

{ $1, p_1, p_2, \dots, p_n$ }

の $n + 1$ 個になる。

#include <iostream>
#include <vector>
using namespace std;

// 素因数分解する 
// たとえば 60 = 2^2 x 3 x 5 だったら {(2, 2), (3, 1), (5, 1)} を返す
vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

// 最大公約数を求める
long long GCD(long long x, long long y) {
    return y ? GCD(y, x%y) : x;
}

int main() {
    long long A, B;
    cin >> A >> B;
    long long G = GCD(A, B);
    auto pf = prime_factorize(G);
    cout << pf.size() + 1 << endl;
}

別解: 最大公約数に思い至らなくても...

ここでは $A, B$ の公約数は「 $A, B$ の最大公約数の約数」であるということを使った。しかしそんなことしなくても

$A$ を素因数分解する
$B$ を素因数分解する

これらの共通に登場する素因数を $p_1, p_2, \dots, p_n$ として $n + 1$ が答え、としても良い。

「公約数」と「最大公約数の約数」が一致することの証明

ちゃんと証明しようと思うとちょっと大変...まず、 $A, B$ の最大公約数を $G$ としたとき、 $G$ の約数 $D$ が $A, B$ の公約数であることは明らか。 $A$ も $B$ も $G$ で割り切れるのだから、当然 $D$ でも割り切れる。

逆はちょっとややこしい。一般に最大公約数の性質として

$Ax + By = G$

を満たす整数 $x, y$ が存在することがいえる (この性質は 600 点問題あたりからかなり登場します)。よって $A, B$ の公約数 $D$ をとってきたとき、 $A, B$ は $D$ で割り切れるので $Ax + By$ も $D$ で割り切れる。すなわち $G$ は $D$ で割り切れる。以上から「公約数」は「最大公約数の約数」であることがいえた。