C++で素因数のべき乗のGCDが1となる範囲内の数を数える方法

正の整数の範囲を表す2つの数 start と end が与えられます。この問題の目標は、範囲 [start, end] に含まれる数のうち、素因数分解した際のすべての素因数の指数（べき乗）の最大公約数（GCD）が 1 となる数の個数を求めることです。

ある数が 2^p × 3^q × 5^r … のように素因数分解できる場合、指数 p, q, r … のGCDが 1 でなければなりません。

例で理解しよう

入力例:

start = 1, end = 10

出力: 素因数のべき乗のGCDが1となる範囲内の数の個数： 6

説明: 該当する数は次のとおりです。

2（2¹）、3（3¹）、5（5¹）、7（7¹）、8（2³）、10（2¹ × 5¹）。それぞれの素因数分解におけるべき乗のGCDはすべて 1 です。

入力例:

start = 11, end = 20

出力: 素因数のべき乗のGCDが1となる範囲内の数の個数： 9

説明: 該当する数は次のとおりです。

11（11¹）、12（3¹ × 2²）、13（13¹）、14（2¹ × 7¹）、15（3¹ × 5¹）、17（17¹）、18（2¹ × 3²）、19（19¹）、20（2² × 5¹）。それぞれの素因数分解におけるべき乗のGCDはすべて 1 です。

プログラムで使用するアプローチ

このアプローチでは、範囲 start ～ end にある「完全累乗数ではない」数をすべて数えます。完全累乗数でない数は、上記の条件（べき乗のGCDが1）を必ず満たすためです。そこで、まず範囲内の完全累乗数をすべて見つけ、総数からそれらを差し引きます。

答え = (end − start + 1) − （範囲 [start, end] 内の完全累乗数の個数）

• 範囲を表す変数 start と end を入力として受け取ります。
• 3以上の奇数べき乗を格納するためのベクター vec を用意します。
• 完全平方数を格納するセット sett を用意します。
• 完全平方数ではない数を格納するセット sett_2 を用意します。
• 関数 calculate() は、ベクター vec およびセット sett、sett_2 を構築し、完全平方数・非完全平方数・3以上の奇数べき乗の数を分類します。
• forループで i = 2 から i < size まで走査します。
• 完全平方数 i*i を sett に挿入します。
• sett.find(i) != sett.end() が true を返す場合、i は完全平方数であり sett に既に存在するため、何もしません。
• 現在の数のべき乗が large 未満である限り、whileループを繰り返します。
• 偶数べき乗は完全平方数として sett に含まれるため、奇数べき乗のみを sett_2 に挿入します。
• 最後に、forループを使って sett_2 のソート済みの値をベクター vec に挿入します。
• 関数 GCD_1(long int start, long int end) は範囲を受け取り、素因数のべき乗のGCDが1となる範囲内の数の個数を返します。
• calculate() を呼び出します。
• 範囲内の完全平方数の個数を per_sq = floor(sqrtl(end)) − floor(sqrtl(start − 1)) として計算します。
• upper_bound(vec.begin(), vec.end(), end) − vec.begin() により、vec 内で end を超える最初の位置（top）を求めます。
• 同様に lower_bound(vec.begin(), vec.end(), start) − vec.begin() により、vec 内で start 以上の最初の位置（bottom）を求めます。
• 完全累乗数の個数を per_pow = per_sq + (top − bottom) として計算します。
• 答えは count = (end − start + 1) − per_pow となります。
• 最後に count を結果として返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define size 1000005
#define large 1e18

vector < long int > vec;
set < long int > sett;
set < long int > sett_2;

void calculate() {
    for (long int i = 2; i < size; i++) {
        sett.insert(i * i);
        if (sett.find(i) != sett.end()) {
            continue;
        }
        long int total = i;
        while (i * i <= large / total) {
            total *= (i * i);
            sett_2.insert(total);
        }
    }
    for (auto it: sett_2) {
        vec.push_back(it);
    }
}

long int GCD_1(long int start, long int end) {
    calculate();

    long int per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1));
    long int top = upper_bound(vec.begin(), vec.end(), end) - vec.begin();
    long int bottom = lower_bound(vec.begin(), vec.end(), start) - vec.begin();
    long int per_pow = per_sq + (top - bottom);
    long int count = (end - start + 1) - per_pow;
    return count;
}
int main() {
    long int start = 10, end = 40;
    cout << "素因数のべき乗のGCDが1となる範囲内の数の個数: " << GCD_1(start, end);
    return 0;
}

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

出力

素因数のべき乗のGCDが1となる範囲内の数の個数: 7