C++でGCDとLCMの値から条件を満たす数のペアの総数を求める方法

この記事では、最大公約数（GCD）と最小公倍数（LCM）の値が与えられたとき、その両方の条件を満たす整数のペアが全部で何通り存在するかを求める方法を解説します。

例として、GCDが2、LCMが12の場合を考えてみましょう。この条件を満たすペアは (2, 12)、(4, 6)、(6, 4)、(12, 2) の4つです。プログラムの目的は、このペアの総数「4」を計算することです。

解決の鍵となる数学的性質

2つの整数 a と b の間には、次のような重要な関係が常に成り立ちます。

a × b = GCD(a, b) × LCM(a, b)

また、a と b はいずれも必ず GCD で割り切れるため、a′ = a ÷ GCD、b′ = b ÷ GCD と置くと、「a′ × b′ = LCM ÷ GCD」が成立し、さらに a′ と b′ は互いに素（共通の約数を持たない）になります。

つまり、LCM ÷ GCD を素因数分解したときに現れるそれぞれの異なる素因数は、a′ と b′ のどちらか一方に丸ごと割り当てるしかありません。素因数の種類が c 個であれば、割り当て方は各素因数ごとに2通りずつ増えていくため、答えは 2^c 通りだと分かります。

なお、LCM が GCD で割り切れない場合には、条件を満たすペアが1つも存在しないため、答えは0になります。

アルゴリズム

以上の性質を踏まえると、この問題は次の手順で解けます。

countPairs(gcd, lcm):
Begin
    if lcm is not divisible by gcd, then
        return 0
    temp := lcm / gcd
    c := primeFactorCount(temp)
    res := shift 1 to the left c times   // 2^c を計算
    return res
End

primeFactorCount(n):   // n の異なる素因数の個数を数える
Begin
    count := 0
    if n is even, then
        count := count + 1
        while n is even, do
            n := n / 2
        done
    end if
    for i := 3, while i^2 <= n, increase i by 2, do
        if n is divisible by i, then
            count := count + 1
            while n is divisible by i, do
                n := n / i
            done
        end if
    done
    if n > 2, then
        count := count + 1
    return count
End

C++による実装例

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

int primeFactorCount(int);

// 条件を満たすペアの総数を返す関数
int countPairs(int gcd, int lcm) {
    // LCMがGCDで割り切れない場合はペアが存在しない
    if(lcm % gcd != 0)
        return 0;
    int temp = lcm / gcd;
    // 素因数の種類数をcとすると、答えは2^c
    return (1 << primeFactorCount(temp));
}

// nの異なる素因数の個数を数える関数
int primeFactorCount(int n){
    int count = 0;
    // まず2で割れるだけ割る
    if(n % 2 == 0){
        count++;
        while(n % 2 == 0)
            n = n / 2;
    }
    // この時点でnは奇数なので、以降は奇数のみ試せばよい
    for(int i = 3; i * i <= n; i = i + 2){
        if(n % i == 0){
            count++;
            while(n % i == 0)
                n = n / i;
        }
    }
    // 2より大きい数が残っていれば、それ自身が素因数
    if(n > 2)
        count++;
    return count;
}

int main() {
    cout << "Possible pairs of GCD = 2, and LCM = 12 is " << countPairs(2, 12);
}

実行結果

Possible pairs of GCD = 2, and LCM = 12 is 4

GCDが2、LCMが12という条件を満たすペアは (2, 12)、(4, 6)、(6, 4)、(12, 2) の4通りなので、プログラムは正しく「4」を出力しています。

計算量について

素因数分解には平方根までの試し割り法を用いているため、全体の時間計算量は O(√(LCM ÷ GCD)) となります。GCDとLCMの値から直接ペアの個数を導出できるため、すべての数の組み合わせを全探索するよりもはるかに効率的な手法です。