C++で解く「醜い数 III」：二分探索と包除原理による効率的な求め方

n番目の「醜い数（Ugly Number）」を求めるプログラムを書くことを考えます。醜い数とは、与えられた整数 a、b、c のいずれかで割り切れる正の整数のことです。

例として、n = 3、a = 2、b = 3、c = 5 の場合を見てみましょう。このとき醜い数は小さい順に [2, 3, 4, 5, 6, 8, 9, 10, …] と並び、3番目の値は 4 となるため、出力は 4 になります。

解法のポイント：二分探索と包除原理

醜い数を順番に生成していくのは非効率です。そこで「ある値 x 以下に醜い数がいくつあるか」を高速に数える手法を使います。

x 以下の醜い数の個数は、次の包除原理によって求められます。

ok(x) = x/a + x/b + x/c − x/lcm(a,b) − x/lcm(b,c) − x/lcm(a,c) + x/lcm(a, lcm(b,c))

ここで lcm(a, b) は a と b の最小公倍数です。まず各数の倍数の個数を足し上げ、次に2つの数の公倍数として二重に数えた分を引き、最後に3つの数すべての公倍数を加え直すことで、正確な個数が得られます。

個数が分かれば、「ok(x) ≥ n となる最小の x」こそが n 番目の醜い数です。ok(x) は x に対して単調増加するため、二分探索でこの x を効率よく絞り込めます。

アルゴリズムの手順

• 関数 ok(x, a, b, c) を定義し、上記の式で x 以下の醜い数の個数を返す。
• 探索範囲を low := 1、high := 2 × 10⁹ に設定する。
• low < high の間、次を繰り返す。
  • mid := low + (high − low) / 2 とする。
  • x := ok(mid, a, b, c) で mid 以下の醜い数の個数を求める。
  • x ≥ n なら high := mid、そうでなければ low := mid + 1 とする。
• ループを抜けたら high を返す。これが n 番目の醜い数です。

C++の実装例

以下に実装例を示します。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    lli gcd(lli a, lli b){
        return b == 0 ? a : gcd(b, a % b);
    }
    lli lcm(lli a, lli b){
        return a * b / gcd(a, b);
    }
    lli ok(lli x, lli a, lli b, lli c){
        return (x / a) + (x / b) + (x / c)
            - (x / lcm(a, b)) - (x / lcm(b, c)) - (x / lcm(a, c))
            + (x / lcm(a, lcm(b, c)));
    }
    int nthUglyNumber(int n, int a, int b, int c) {
        int low = 1;
        int high = 2 * (int) 1e9;
        while(low < high){
            int mid = low + (high - low) / 2;
            int x = ok(mid, a, b, c);
            if(x >= n){
                high = mid;
            }
            else low = mid + 1;
        }
        return high;
    }
};
main(){
    Solution ob;
    cout << (ob.nthUglyNumber(3,2,3,5));
}

入力

3
2
3
5

出力

4

gcd() はユークリッドの互除法で最大公約数を、lcm() はその結果を利用して最小公倍数をそれぞれ計算します。ok() の中で a・b・c の組み合わせごとの最小公倍数を用いて包除原理どおりに個数を算出し、それを二分探索に組み合わせることで、大きな n に対しても高速に答えを求められるのがこの解法の魅力です。