【C++】オイラーのトーティエント関数で1からNまでの互いに素なペアの数を数える

問題概要

この問題では、それぞれ異なる数値 N を含む Q 個のクエリ が与えられます。求めるのは、1 から N までの範囲に存在する「順序を区別しない互いに素なペア」の総数です。本記事では、これを効率的に解く C++ プログラムを紹介します。

互いに素（コプライム / coprime）は、相対素数・相互素数とも呼ばれ、共通の約数が 1 のみであるような 2 つの数の組み合わせを指します。たとえば (3, 4) は最大公約数が 1 なので互いに素ですが、(4, 6) は公約数に 2 を持つため互いに素ではありません。

具体例で理解しよう

N = 5 の場合を考えてみましょう。

出力: 10

条件を満たすペアは次の 10 組です。
(1, 1)、(1, 2)、(1, 3)、(1, 4)、(1, 5)、(2, 3)、(2, 5)、(3, 4)、(3, 5)、(4, 5)

解法のアプローチ：オイラーのトーティエント関数

この問題を解く鍵となるのがオイラーのトーティエント関数（Euler's Totient Function）です。φ(N) は「1 以上 N 以下の整数のうち、N と互いに素なものの個数」を返します。

オイラーのトーティエント関数は次の式で定義されます。

φ(N) = N × Π (1 − 1/p)

ここで p は N のすべての素因数を表します。

さらに重要なのが次の性質です。

1 から N までの順序なし互いに素なペアの総数 = Σ φ(i)（i = 1 … N）

これは、各 i について「i 以下で i と互いに素な整数の個数」がちょうど φ(i) になるためです。したがって、あらかじめ φ の値とその累積和を配列として計算しておけば、各クエリには配列参照 1 回（O(1)）で回答できます。前計算はエラトステネスの篩と同様の考え方で行うため、全体の計算量も O(N log log N) 程度に抑えられます。

C++ での実装例

#include <iostream>
using namespace std;
#define N 10001
int phi[N];
int CoPrimePairs[N];

void computePhi() {
    for (int i = 1; i < N; i++)
        phi[i] = i;
    for (int p = 2; p < N; p++) {
        if (phi[p] == p) { // p は素数
            phi[p] = p - 1;
            for (int i = 2 * p; i < N; i += p) {
                phi[i] = (phi[i] / p) * (p - 1);
            }
        }
    }
}

void findCoPrimes() {
    computePhi();
    for (int i = 1; i < N; i++)
        CoPrimePairs[i] = CoPrimePairs[i - 1] + phi[i]; // 累積和
}

int main() {
    findCoPrimes();
    int Q = 3;
    int query[] = { 5, 7, 9 };
    for (int i = 0; i < Q; i++)
        cout << "For Query " << (i + 1) << ": Number of prime pairs is " << CoPrimePairs[query[i]] << endl;
    return 0;
}

コードのポイント

• computePhi()：篩のアルゴリズムのように素数 p を検出し、p の倍数すべてに対して φ の値を更新していきます。
• findCoPrimes()：φ(i) の累積和を CoPrimePairs 配列に格納することで、任意の N に対する答えを即座に取得できるようにしています。
• 計算量：前計算は O(N log log N)、以降の各クエリへの応答は O(1)。

実行結果

For Query 1: Number of prime pairs is 10
For Query 2: Number of prime pairs is 18
For Query 3: Number of prime pairs is 28

N = 5 のとき 10 組、N = 7 のとき 18 組、N = 9 のとき 28 組となり、正しくペア数が求められていることが確認できます。

まとめ

複数のクエリで「1 から N までの互いに素なペアの数」を求める場合は、オイラーのトーティエント関数を事前に一括計算し、累積和を持っておくのが最も効率的です。篩の手法で前計算を行えば、以降のクエリには瞬時に回答でき、競技プログラミングなどでも活用できる強力なテクニックです。