ในปัญหานี้ เราได้รับจำนวนธรรมชาติ N หน้าที่ของเราคือ หาผลรวมของตัวหารของตัวหารทั้งหมดของจำนวนธรรมชาติ .
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : N = 12 Output : 55
คำอธิบาย −
The divisors of 12 are 1, 2, 3, 4, 6, 12 Sum of divisors = (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
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการใช้การแยกตัวประกอบของ 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
