AcWing 870. 约数个数
原题链接
简单
作者:
大海呀大海
,
2020-07-25 18:44:55
,
所有人可见
,
阅读 561
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int N = 110, mod = 1e9 + 7;
int main(){
int n;
cin >> n;
unordered_map<int, int> primes;//给每一个约数出现的次数计数
//first 为 约数,second 为 约数的个数
while (n -- ){
int x;
cin >> x;
for (int i = 2; i <= x / i; i ++ ){
while (x % i == 0){//如果存在约数
x /= i;
primes[i] ++;//将约数计数
}
}
if (x > 1) primes[x] ++;//一定要注意这一点,因为for和while到了最后,可能就剩下一个数了,要判断一下
//比如12,12->3,x=12先被while变成x = 3,然后i=3,但是i大于x/3 = 3/3 = 1;不满足条件
}
ll res = 1;
for (auto prime : primes) res = res * (prime.second + 1) % mod;//将所有的约数都给算一下
cout << res << endl;
return 0;
}