Trong bài toán này, chúng ta được cho một số tự nhiên N. Nhiệm vụ của chúng ta là tìm tổng các ước của tất cả các ước của một số tự nhiên .
Hãy lấy một ví dụ để hiểu vấn đề,
Input : N = 12 Output : 55
Giải thích -
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
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng thừa số N. Sử dụng thừa số nguyên tố, chúng ta có thể tìm tổng các ước của tất cả các ước. Ở đây, chúng ta sẽ tìm thừa số nguyên tố của mỗi phần tử.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The sum of divisors of all divisors is 55