如何求一个数约数的个数以及如何求一个数约数的和:基于算数基本定理
题目一:约数个数
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod = 1e9 + 7; 5 int main() { 6 int n; 7 cin >> n; 8 unordered_map<int, int> primes; //存储所有底数和指数 9 while (n--) { 10 int x; 11 cin >> x; 12 for (int i = 2; i <= x / i; i++) { 13 while (x % i == 0) { 14 x /= i; 15 primes[i]++; 16 } 17 } 18 if (x > 1) { 19 primes[x]++; 20 } 21 } 22 ll res = 1; 23 //不用c++11新特性的auto的unordered_map的遍历方式 24 for (unordered_map<int, int>::iterator it = primes.begin(); it != primes.end(); it++) { 25 res = res * (it -> second + 1) % mod; 26 } 27 cout << res << endl; 28 return 0; 29 }
题目二:约数之和
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod = 1e9 + 7; 5 int main() { 6 int n; 7 cin >> n; 8 unordered_map<int, int> primes; 9 while (n--) { 10 int x; 11 cin >> x; 12 for (int i = 2; i <= x / i; i++) { 13 while (x % i == 0) { 14 x /= i; 15 primes[i]++; 16 } 17 } 18 if (x > 1) { 19 primes[x]++; 20 } 21 } 22 ll res = 1; 23 for (unordered_map<int, int>::iterator it = primes.begin(); it != primes.end(); it++) { 24 int p = it -> first, a = it -> second; 25 //p是底数,a是指数 26 ll t = 1; //t是当前这个数p的0 ~ a1次方相加 27 while (a--) { //执行a次 28 t = (t * p + 1) % mod; 29 } 30 res = res * t % mod; 31 } 32 cout << res << endl; 33 return 0; 34 }