ในปัญหานี้ เราได้รับจำนวนธรรมชาติ N งานของเราคือ การหาผลรวมของตัวหารของทุกตัวหารของจำนวน N
ตัวอย่างเพื่อความเข้าใจ
Input : N = 12 Output : 55
คำอธิบาย
ตัวหารของ 12 คือ 1, 2, 3, 4, 6, 12 ผลรวมตัวหาร = (1) + (1+2) + (1+3) + (1+2+4) + (1+2+3+6) + (1+2+3+4+6+12) = 1 + 3 + 4 + 7 + 12 + 28 = 55
แนวทางแก้ปัญหา
วิธีแก้ที่ง่ายคือการแยกตัวประกอบเฉพาะ (prime factorization) ของ N โดยใช้การแยกตัวประกอบเฉพาะ เราสามารถหาผลรวมของตัวหารของทุกตัวหารได้
ตัวอย่างโค้ด
โปรแกรมตัวอย่างสำหรับการทำงานของวิธีแก้ปัญหา
#include <bits/stdc++.h>
using namespace std;
int findSumOfDivisorsOfDivisors(int n) {
map<int, int> factorCount;
for (int j = 2; j <= sqrt(n); j++) {
int count = 0;
while (n % j == 0) {
n /= j;
count++;
}
if (count)
factorCount[j] = count;
}
if (n != 1)
factorCount[n] = 1;
int sumOfDiv = 1;
for (auto it : factorCount) {
int power = 1;
int sum = 0;
for (int i = it.second + 1; i >= 1; i--) {
sum += (i * power);
power *= it.first;
}
sumOfDiv *= sum;
}
return sumOfDiv;
}
int main() {
int n = 12;
cout << "The sum of divisors of all divisors is " << findSumOfDivisorsOfDivisors(n);
return 0;
}
ผลลัพธ์
The sum of divisors of all divisors is 55
