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 số của tất cả ước số của một số tự nhiên.
Hãy xem ví dụ sau để hiểu bài toán:
Input : N = 12 Output : 55
Giải thích −
Các ước của 12 là 1, 2, 3, 4, 6, 12 Tổng ước = (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 giải
Một giải pháp đơn giản là sử dụng phân tích thừa số nguyên tố của N. Sử dụng phân tích nguyên tố, ta có thể tìm tổng các ước số của tất cả các ước. Ở đây, ta sẽ tìm phân tích nguyên tố của từng phần tử.
Ví dụ
Chương trình minh họa cho giải pháp
#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; }Kết quả
The sum of divisors of all divisors is 55