ABC 142 D - Disjoint Set of Common Divisors 解説

atcoder.jp

題意

2つの正整数A、Bが与えられるので、その公約数のうちいくつかを選ぶ。
このとき選んだ値は、それぞれが互いに素である必要がある。
選べる公約数の最大の個数はいくつか？

制約

1 <= A, B <= 10¹²

考えたこと

互いに素である、というのは2つの整数が1以外に公約数を持たないことを指します。

この定義から、AとBの公約数からそれぞれが互いに素である数を選び取っていくには、約数の中から素数を選び取っていけばよいと考えられます。
これなぜかというと、素数以外の約数を選択する場合を考えると素数である約数を選択する場合に比べて、損をすることはあっても得をすることはないとわかるからです。

例として、A=6, B=12の場合を考えます。その公約数は、1, 2, 3, 6なります。
素数のみを選択した場合、2, 3を選択することになり、1を含めると公約数は合計3個を選ぶことができます。
一方、素数ではない6を選ぶ場合、2, 3と共通の約数を持つため、1を含めて合計2個となり、素数を選ぶ場合より1個損です。

上記のように素数以外の約数を選択すると、その数の1以外の約数を選択できなくなるため、素数である約数を選択する場合に比べて不利であるとわかります。
よって、A、Bの素数である公約数、つまり、素因数を数えることで、解が得られると判断できそうです。

では、2数の素因数の求め方ですが、これは以下の2つの手順で効率的に求めることができます。


1. 最大公約数Gを求める 2. 試し割り法により、2～√Gの値にある素因数を求める

最大公約数はユークリッドの互除法により、効率的に求めることができます。

さて、最大公約数を求めた後の試し割り法が重要です。
最大公約数Gを求めて、2～Gまで愚直に素因数判定を行うと（O(G)）、AとBが同じ値で10¹²に近い素数であった場合、Gはその素数となります。このままでは間に合いません。

そこで、試し割り法という工夫を適用します。
これは、整数Gの素因数を調べるのにGまで調べる必要はなく、√Gまでを調べれば良いというものです。（詳しくはリンク先を参照）

これでループ部分の時間計算量を√Gまで落とすことができ、実行時間に間に合うようになります。

実装

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// greatest common divisor (最大公約数)
ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }

int main(){
  
  // input
  
  ll a,b; cin>>a>>b;          // a, bの上限は10^12であることに注意
  
  // solution
  
  ll G=GCD(a,b);

  ll ans=1;                   // a, bがどのような値でも、1は必ず選ぶことができる
  
  for(ll i=2; i*i<=G; i++){   // √Gまでループを行い素因数判定を行う
    
    if(G%i==0){               // 素因数判定
      ans++;
      while(G%i==0) G/=i;     // Gの素因数からiを除外していく
    }
    
  }
  
  if(G!=1) ans++;             // √Gのループを抜けた時Cが1でないならば、その時のGは素数である
  
  cout<<ans<<endl;
  
}

感想

• GCD（ユークリッドの互除法）
• 素因数分解（試し割り法）

教養的知識を2つ組み合わせて解く、アカデミックな内容でとても面白かったです。
問題を読んですぐに方針は立てられたものの、実装に時間が掛かってしまったので、GCDや素因数分解などのアルゴリズムの基本とも言えるものについては、ライブラリ化するだけではなく、いつでも書けるようにしておく必要がある、と学びになりました。

......ところで、「互いに素」という単語を見聞きして、私はリズと青い鳥を連想します。

リズと青い鳥[Blu-ray]