C++で、xとx+1が同じ個数の約数を持つ範囲(1, N)内の整数xの個数を求める方法

整数 N が与えられたとき、1 < x < N を満たす整数 x のうち、x と x+1 が同じ個数の正の約数を持つものがいくつあるかを求めます。

例えば N = 3 の場合、出力は 1 になります。これは、2 の約数が 1 と 2 の 2 個、3 の約数が 1 と 3 の 2 個であり、両者とも約数の個数が等しいためです。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

1. N 未満のすべての整数について、約数の個数を事前に計算して配列に格納します。
2. 隣り合う数（x と x+1）の約数の個数を比較し、等しくなる箇所を数えます。
3. 累積和（prefix sum）を取っておくことで、任意の N に対する答えを O(1) で取得できるようにします。

約数の個数を求める際は、√i までの整数で試し割りを行うことで計算量を抑えています。j が i の約数であれば i/j も必ず約数になるため、j × j = i となる場合（平方数）は 1 個、それ以外の場合は 2 個をカウントします。

実装例（C++）

#include<iostream>
#include<cmath>
#define N 100005
using namespace std;
int table[N], pre[N];
void findPositiveDivisor() {
    for (int i = 1; i < N; i++) {
        for (int j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                if (j * j == i)
                    table[i]++;
                else
                    table[i] += 2;
            }
        }
    }
    int ans = 0;
    for (int i = 2; i < N; i++) {
        if (table[i] == table[i - 1])
            ans++;
        pre[i] = ans;
    }
}
int main() {
    findPositiveDivisor();
    int n = 15;
    cout << "Number of integers: " << pre[n] << endl;
}

出力

Number of integers: 2

この例では N = 15 としており、条件を満たすのは x = 2（2 と 3 の組）と x = 14（14 と 15 の組）の 2 つです。2 と 3 はどちらも約数を 2 個持ち、14 と 15 もどちらも約数を 4 個持つためです。

計算量

前計算には O(N√N) の時間がかかりますが、一度計算してしまえば、以降はどの N についても O(1) で答えを取得できます。複数のクエリを処理する場合に特に有効な手法です。