すごく楽しくて教育的な整数問題
問題概要
2 つの正の整数 が与えられる。 の公約数から何個か整数を選ぶことを考える。
選んだ整数からどの 2 つをとっても、それらが互いに素になるようにしたい。
選べる個数の最大値を求めよ。
制約
考えたこと
まずそもそも、どうすれば の公約数を列挙できるのかを考えてみたい。実は
- の公約数を列挙したもの
- の最大公約数を として の約数を列挙したもの
は完璧に一致するのだ。ちょっとその感触をつかんでみたい。
たとえば 36 と 48 の公約数は
1, 2, 3, 4, 6, 12
である。これはちょうど 36 と 48 の最大公約数である 12 の約数になっている!!!この事実は直感的には明らかだし、実は高校数学で無意識にそう思ってた方も多いと思う。(一応一番下で証明を載せた)。
なお、「公約数は最大公約数の約数」を知らなくても解く方法もある (それも下に載せた)。
シンプルな問題に
以上から問題は の最大公約数を として
- の約数から何個か選びたい
- 選んだ整数たちのどの 2 つをとっても互いに素になるようにしたい
- 最大で何個選べるか
という問題に帰着された。これは一見難しく見えるが、素因数分解のことを知っていれば実はそんなに難しくない。なお素因数分解は でできるのだが、そのやり方は、たとえば蟻本や螺旋本に載っている。
さて、たとえば としてみよう。 である。そうすると の約数は以下の 12 個になる:
つまり、 (、、) が約数の全体になる。
そして互いに素ということは「共通の素因数を持たない」ということ。つまり
は互いに素だが
は「3」が被っているので互いに素ではない。
では、 の約数から互いに素になるように、なるべく多く選ぼうと思うと
と選べば良さそうという直感がはたらく。まず は絶対入れる。これはいかなる整数とも互いに素なので入れて損はない。1 以外は「素因数分解に出てくる素因数」を並べると良さそう。
一応、これを超えることはできないことをちゃんと証明しておきたい。60 の約数に含まれる素因数は 2, 3, 5 以外にはありえない。よって、1 を除くと、約数を 1 個選ぶたびに、1 個以上の素因数を潰すことになる。たとえば を選ぶと素因数は 2 のみだから 2 を潰す (今後 2 を素因数に含む奴は二度と選べなくなる)。 を選ぶと素因数は 2, 3 だから 2 と 3 を潰すことになる。
そうすると、1 を除くと、たかだか 3 個までしか選べない!!!
一般化すると、 を素因数分解に登場する素因数が の 個があったとすると、答えは
- { }
の 個になる。
#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; }
別解: 最大公約数に思い至らなくても...
ここでは の公約数は「 の最大公約数の約数」であるということを使った。しかしそんなことしなくても
これらの共通に登場する素因数を として が答え、としても良い。
「公約数」と「最大公約数の約数」が一致することの証明
ちゃんと証明しようと思うとちょっと大変...まず、 の最大公約数を としたとき、 の約数 が の公約数であることは明らか。 も も で割り切れるのだから、当然 でも割り切れる。
逆はちょっとややこしい。一般に最大公約数の性質として
を満たす整数 が存在することがいえる (この性質は 600 点問題あたりからかなり登場します)。よって の公約数 をとってきたとき、 は で割り切れるので も で割り切れる。すなわち は で割り切れる。以上から「公約数」は「最大公約数の約数」であることがいえた。