การสืบค้นผลรวมของผลรวมหลักฐานคี่ของตัวประกอบใน C++

ในโปรแกรมนี้ เราได้รับ Q queries แต่ละ query มีจำนวนเต็มบวก N ภารกิจคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นผลรวมของผลรวมหลักฐานคี่ของตัวประกอบทั้งหมดของตัวเลขใน C++

คำอธิบายปัญหา

เพื่อแก้แต่ละ query เราต้องหาตัวประกอบทั้งหมดของตัวเลข N จากนั้นรวมตัวประกอบที่มีผลรวมของหลักฐานเป็นเลขคี่ และคืนค่าผลรวมสุดท้ายสำหรับแต่ละ query

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต

Q = 2, queries = {15, 8}

เอาต์พุต

8 1

คำอธิบาย

Query 1: N = 15, ตัวประกอบของ 15 คือ 1, 3, 5, 15

ผลรวมของหลักฐานคี่ในตัวประกอบคือ 1 + 3 + 5 = 8

Query 2: N = 8, ตัวประกอบของ 8 คือ 1, 2, 4, 8

ผลรวมของหลักฐานคี่ในตัวประกอบคือ 1 = 1

แนวทางแก้ปัญหา

เพื่อแก้ปัญหานี้ เราต้องหาผลรวมของหลักฐานคี่ของทุกตัวเลข ซึ่งเราจะใช้คำนวณตัวประกอบและรวมกัน สำหรับการคำนวณผลรวมหลักฐาน เราสามารถใช้ค่าที่คำนวณไว้ล่วงหน้า (precomputed) ได้ เช่น ผลรวมหลักฐานคี่ของ 41 สามารถหาได้จาก ผลรวมหลักฐานคี่ของ 4 + หลักฐานคี่ของ 1

หลังจากสร้างอาร์เรย์ oddDigitSum แล้ว เราจะหาตัวเลขทั้งหมดที่หารตัวเลขที่กำหนดลงตัว จากนั้นรวมผลรวมหลักฐานคี่โดยใช้ oddDigitSum array

ตัวอย่างโปรแกรม

#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