けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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
  •  2
  •  3
  •  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 の最大公約数の約数」であるということを使った。しかしそんなことしなくても

これらの共通に登場する素因数を  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 で割り切れる。以上から「公約数」は「最大公約数の約数」であることがいえた。