C++で解く：数のすべての約数に含まれる奇数桁の和の総和を求めるクエリ処理

本記事では、Q個のクエリを処理するプログラムを扱います。各クエリには正整数Nが与えられ、C++を用いて「Nのすべての約数に含まれる奇数の桁の和」の総和を求める方法を解説します。

問題の概要

各クエリを処理する手順は次のとおりです。まず数Nのすべての約数を求めます。続いて、各約数ごとに「奇数の数字のみを足し合わせた値（奇数桁の和）」を計算し、それらをすべて合計した結果を返します。

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

入力

Q = 2, queries = {15, 8}

出力

15 1

計算の内訳

クエリ1：N = 15 の場合。15の約数は 1, 3, 5, 15 です。
各約数の奇数桁の和は、それぞれ 1、3、5、そして 15 の場合は 1 + 5 = 6 となります。
よって合計は 1 + 3 + 5 + 6 = 15 です。

クエリ2：N = 8 の場合。8の約数は 1, 2, 4, 8 です。
このうち奇数の数字を含むのは 1 だけであり、偶数の桁は無視されるため、合計は 1 となります。

解法のアプローチ

この問題を効率よく解く鍵となるのが、奇数桁の和の前計算です。各数の奇数桁の和は、次のような漸化式で求められます。

「i の奇数桁の和」＝「i を 10 で割った商の奇数桁の和」＋「i が奇数のときのみ、最下位の桁（i % 10）の値」。たとえば 41 の奇数桁の和は、「4 の部分の奇数桁の和」に「最下位の桁 1 が奇数であるためその値を加える」ことで得られます。これを配列 oddDigitSum として事前に構築しておきます。

次に、各数の約数をすべて列挙し、oddDigitSum 配列を参照しながら約数ごとの奇数桁の和を加算していきます。約数の列挙には、「i のすべての倍数に対して i を約数として加算していく」というふるい方式を採用すると、対象範囲内のすべての数についての結果を一括で前計算できます。

ソリューションの実装例

#include <iostream>
using namespace std;
#define N 99999

void calcOddDigitSum(int oddDigitSum[]) {

    for (int i = 1; i < N; i++)
    oddDigitSum[i] = oddDigitSum[i / 10] + (i & 1) * (i % 10);
}

void findFactorSum(int oddDigitSum[], int factorSum[]) {

    for (int i = 1; i < N; i++)
    for (int j = i; j < N; j += i)
    factorSum[j] += oddDigitSum[i];
}

int main(){
    int Q = 3;
    int query[] = { 5, 154, 98 };
    int oddDigitSum[N];
    int factorSum[N];
    calcOddDigitSum(oddDigitSum);
    findFactorSum(oddDigitSum, factorSum);
    for (int i = 0; i < Q; i++)
    cout<<"For query "<<(i+1)<<": The sum of odd number digit sums of all the factors of a number is "<<factorSum[query[i]]<<endl;
    return 0;
}

実行結果

For query 1: The sum of odd number digit sums of all the factors of a number is 6
For query 2: The sum of odd number digit sums of all the factors of a number is 31
For query 3: The sum of odd number digit sums of all the factors of a number is 27

計算量とポイント

calcOddDigitSum 関数は各数を一度ずつ処理するため O(N) で動作します。findFactorSum 関数は約数の個数が調和級数的に増える性質を利用しており、全体で O(N log N) の計算量に収まります。これらの前計算を完了させておけば、各クエリには配列を参照するだけで O(1) で回答できるため、同一の上限範囲内で多数のクエリを処理する場合に非常に効率的な手法といえます。