约数个数
约数和定理:
对于一个大于1正整数n可以分解质因数
$$ n=\prod_{i=1}^kp_i^{a_i}=p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$$
则n的正约数的个数就是
$$ f(n)=\prod_{i=1}^k(a_i+1)=(a_1+1) \cdot (a_2+1) \cdots (a_k+1) $$
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;
/**
* acwing 870-约数个数
*/
int main() {
int n;
scanf("%d", &n);
unordered_map<int, int> primes;
while (n--) {
int x;
scanf("%d", &x);
for (int i = 2; i <= x / i; i++) {
while (x % i == 0) {
x /= i;
primes[i]++;
}
}
if (x > 1) primes[x]++;
}
LL res = 1;
for (auto prime : primes) {
res = res * (prime.second + 1) % MOD;
}
cout << res << endl;
return 0;
}