(2)约数个数
题目:给定n个正整数ai,请你输出这些数的乘积的约数个数,答案对109+7取模。
算法思想:
基于算数基本定理:N = p~1~^a1^ * p~2~^a2^ * .. * p~k~^ak^
N的任意一项约数可以写成 d = q~1~^b1^+q~2~^b2^+…+q~k~^bk^
不同的b数组组合而成的约数d是不同(即因式分解不同)
同理不同的a数组组合而成的N也是不同的,
而a1有a1+1种选法,a2有a2+1种选法.....ak有ak+1种选法
因此约数个数:(a~1~+1)(a~1~+1)(a~3~+1)…(a~k~+1)
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int P = 1e9 + 7;
int main()
{
unordered_map<int , int> primes; //利用哈希表存储
int n;
cin >> n;
while(n --) //分解质因数
{
int x;
cin >> x;
for(int i = 2 ; i <= x / i; i++)
{
while(x % i == 0)
{
primes[i]++;
x /= i;
}
}
if(x > 1) primes[x]++;
}
ll ans = 1;
for(auto p : primes) //迭代一次,套用公式即可
ans = ans * (p.second + 1) % P;
cout << ans << endl;
return 0;
}