C++で積がN未満となる順序対の個数をカウントする方法

問題概要

整数 N が与えられたとき、2つの正の整数からなる順序対(ペア)のうち、その積がN未満になるものをすべて数え上げることを目標とします。

この問題は、i を 1 から N 未満まで、j を 1 から i*j < N を満たす範囲まで動かしながら、条件を満たす組み合わせの数をカウントしていくことで解けます。

具体的な例で確認してみましょう。

入力例 1

N=4

出力例 1

Ordered pairs such that product is less than N: 5

説明

Pairs will be (1,1) (1,2) (1,3) (2,1) (3,1)

積が4未満となる順序対は (1,1)、(1,2)、(1,3)、(2,1)、(3,1) の5つです。順序対であるため、(1,2) と (2,1) は異なるペアとして別々にカウントされる点に注意してください。

入力例 2

N=100

出力例 2

Ordered pairs such that product is less than N: 473

説明

Pairs will be (1,1) (1,2) (1,3)....(97,1), (98,1), (99,1). Total 473.

アルゴリズムのアプローチ

• 整数 N を入力として受け取ります。
• 関数 productN(int n) は引数 n を受け取り、積が n 未満となる順序対の個数を返します。
• ペアの個数を保持する変数 count を 0 で初期化します。
• 2重の for ループを使ってペアを生成していきます。
• 外側のループは i = 1 から i < n まで、内側のループは j = 1 から (i * j) < n を満たす間だけ回します。
• 条件を満たすたびに count を 1 ずつ増加させます。
• すべてのループが完了した時点で、count には該当する順序対の総数が格納されています。
• count を結果として返します。

C++実装例

#include <bits/stdc++.h>
using namespace std;
int productN(int n){
    int count = 0;
    for (int i = 1; i < n; i++){
        for(int j = 1; (i*j) < n; j++)
            { count++; }
    }
    return count;
}
int main(){
    int N = 6;
    cout <<"Ordered pairs such that product is less than N:"<<productN(N);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

Ordered pairs such that product is less than N:10

計算量について

外側のループは最大 N−1 回、内側のループは各 i に対して最大 ⌊(N−1)/i⌋ 回実行されるため、この実装の時間計算量は O(N log N) 程度となります。

また、求めたい個数は数学的には Σ⌊(N−1)/i⌋(i = 1 〜 N−1)として表せます。これは「xy ≤ m となる格子点の個数」を数える問題と同じであり、区間ごとにまとめて計算するブロック分割(ハイパボラ法)などのテクニックを用いれば、O(√N) まで高速化することも可能です。大きな N を扱う場合は、こうした最適化を検討するとよいでしょう。