Truy vấn tổng chữ số lẻ của các ước số trong C++

Trong chương trình này, ta được cho Q truy vấn, mỗi truy vấn là một số nguyên dương N. Nhiệm vụ là tạo chương trình giải quyết truy vấn: tính tổng chữ số lẻ của tất cả các ước số của N trong C++.

Mô tả bài toán

Để giải mỗi truy vấn, ta cần tìm tất cả ước số của số N. Sau đó cộng dồn các ước số mà tổng chữ số của chúng là số lẻ. Trả về tổng cuối cùng cho mỗi truy vấn.

Ví dụ minh họa

Đầu vào

Q = 2, queries = {15, 8}

Đầu ra

8 1

Giải thích

Truy vấn 1: N = 15, ước số của 15 là 1, 3, 5, 15. Tổng chữ số lẻ trong các ước số: 1 + 3 + 5 = 9? (Lưu ý: 15 có chữ số 1 và 5, đều lẻ, tổng = 6. Nhưng ví dụ nói 1+3+5=8, có vẻ chỉ lấy các ước số một chữ số?). Cần làm rõ: "sum of odd number digit sums" nghĩa là tổng của (tổng chữ số lẻ của mỗi ước số). Với 15: ước số 1→1, 3→3, 5→5, 15→1+5=6. Tổng = 1+3+5+6=15. Nhưng ví dụ output 8. Có thể hiểu là: chỉ lấy các ước số mà chính nó là số lẻ? 1,3,5,15 đều lẻ, tổng = 24. Không khớp. Xem lại: "sum of odd digits in factors is 1 + 3 + 5 = 8" – họ chỉ lấy các ước số một chữ số và lẻ? 1,3,5 là ước số một chữ số lẻ, 15 là hai chữ số. Tổng 1+3+5=9? Vẫn không khớp 8. Có thể lỗi ví dụ gốc. Ta sẽ dịch theo logic code: tính tổng chữ số lẻ của từng ước số, rồi cộng dồn.

Truy vấn 2: N = 8, ước số: 1, 2, 4, 8. Tổng chữ số lẻ: 1 = 1.

Phương pháp giải

Để giải bài toán, ta cần tính tổng chữ số lẻ của các số. Từ đó tìm ước số và cộng dồn. Để tối ưu, ta tiền tính mảng oddDigitSum lưu tổng chữ số lẻ cho mỗi số. Ví dụ: tổng chữ số lẻ của 41 = tổng chữ số lẻ của 4 + tổng chữ số lẻ của 1.

Sau khi có mảng oddDigitSum, ta dùng sàng để cộng dồn vào mảng factorSum: với mỗi i, duyệt các bội số j của i và cộng oddDigitSum[i] vào factorSum[j].

Chương trình minh họa:

Ví dụ

#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;
}

Đầu ra

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