이 프로그램에서는 Q 쿼리가 제공되며 각 쿼리에는 양의 정수 N이 있습니다. 우리의 임무는 C++에서 숫자의 모든 요소에 대한 홀수 자릿수 합계에 대한 쿼리를 해결하는 프로그램을 만드는 것입니다.
문제 설명 − 각 쿼리를 해결하려면 숫자 N의 모든 인수를 찾아야 합니다. 그런 다음 자릿수 합이 홀수인 모든 인수를 추가합니다. 그리고 각 쿼리에 대한 최종 합계를 반환합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
Q = 2, queries = {15, 8} 출력
8 1
설명
쿼리 1:N =15의 경우 15의 인수는 1, 3, 5, 15입니다.
인수의 홀수의 합은 1 + 3 + 5 =8입니다.
쿼리 2:N =8의 경우 8의 인수는 1, 2, 4, 8입니다.
인수의 홀수의 합은 1 =1입니다.
해결 방법
이 문제를 해결하려면 모든 숫자의 홀수 자릿수를 더해야 합니다. 여기에서 요인을 계산한 다음 결과에 추가합니다. 이 자릿수 프로세스의 합을 각각 미리 계산된 값을 사용할 수 있습니다. 예를 들어, 숫자 41의 합은 4의 홀수 자릿수 + 3의 홀수 자릿수의 합으로 찾을 수 있습니다.
oddDigitSum 배열을 만든 후 주어진 숫자를 나눌 수 있는 모든 숫자를 찾습니다. 그런 다음, theoddDigitSum 배열을 사용하여 모든 홀수를 추가합니다.
우리 솔루션의 작동을 설명하는 프로그램
예
#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