C++에서 숫자의 모든 약수에 대한 홀수 자릿수 합 쿼리 처리하기

이 글에서는 Q개의 쿼리가 주어지고, 각 쿼리마다 양의 정수 N이 제공될 때, N의 모든 약수 중에서 자릿수의 합이 홀수인 약수들을 골라 그 합을 구하는 프로그램을 C++로 작성하는 방법을 알아봅니다.

문제 설명

각 쿼리를 처리하려면 먼저 N의 모든 약수를 구해야 합니다. 그중 자릿수의 합이 홀수인 약수만 선택하여 모두 더한 뒤, 쿼리별로 최종 합을 반환하면 됩니다.

예제를 통해 문제를 살펴보겠습니다.

입력

Q = 2, queries = {15, 8}

출력

8 1

설명

쿼리 1: N = 15인 경우, 15의 약수는 1, 3, 5, 15입니다.
자릿수 합이 홀수인 약수는 1, 3, 5이며, 따라서 답은 1 + 3 + 5 = 8입니다.

쿼리 2: N = 8인 경우, 8의 약수는 1, 2, 4, 8입니다.
자릿수 합이 홀수인 약수는 1뿐이므로 답은 1입니다.

접근 방법

이 문제를 효율적으로 풀려면 1부터 N-1까지 모든 수에 대해 홀수 자릿수의 합을 미리 계산해 두는 것이 좋습니다. 미리 계산된 배열을 활용하면 각 쿼리마다 자릿수를 일일이 더하는 번거로움을 피할 수 있습니다.

예를 들어 41의 홀수 자릿수 합은 다음과 같이 구할 수 있습니다. 41을 10으로 나눈 몫인 4의 홀수 자릿수 합(0)에, 마지막 자릿수 1이 홀수이므로 1을 더해 최종값 1을 얻습니다. 즉, oddDigitSum[i] = oddDigitSum[i / 10] + (마지막 자릿수가 홀수라면 그 자릿수)라는 점화식으로 누적 계산할 수 있습니다.

oddDigitSum 배열을 완성한 뒤에는 에라토스테네스의 체와 비슷한 방식으로, 각 수 i가 약수가 되는 모든 배수 j에 대해 factorSum[j]에 oddDigitSum[i]를 더해 줍니다. 이렇게 하면 factorSum[j]에는 j의 모든 약수에 대한 홀수 자릿수 합의 총합이 저장되어, 이후 쿼리를 O(1)에 처리할 수 있습니다.

위 접근 방식의 동작을 보여주는 프로그램입니다.

예제 코드

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

// 1부터 N-1까지 각 수의 홀수 자릿수 합을 미리 계산
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 << "쿼리 " << (i + 1) << ": 수의 모든 약수 중 홀수 자릿수 합은 "
             << factorSum[query[i]] << endl;
    return 0;
}

출력 결과

쿼리 1: 수의 모든 약수 중 홀수 자릿수 합은 6
쿼리 2: 수의 모든 약수 중 홀수 자릿수 합은 31
쿼리 3: 수의 모든 약수 중 홀수 자릿수 합은 27

복잡도 분석

홀수 자릿수 합 전처리에는 O(N)의 시간이 걸리고, 약수별 합을 채우는 과정은 조화급수 형태로 O(N log N)의 시간이 소요됩니다. 반면 전처리가 끝난 후에는 각 쿼리를 O(1)에 즉시 응답할 수 있어, 쿼리 개수가 많은 경우에도 매우 효율적입니다.