先计算出所有数,共同的质因数,以及有多少次方。
计算不同的因数和
一些笔记:
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
unordered_map<int, int> primes;
// 传入一个数,把他的质因数和次方加到总的 质因数和次方序列里面
void findPrimeFactors(int n)
{
for (int i = 2; i <= n / i; i++)
if(n % i == 0)
while(n % i == 0)
{
n /= i;
primes[i] ++;
}
if (n > 1) primes[n] ++;
}
int main()
{
int n;
cin >> n;
LL res = 1;
while (n --)
{
int a;
cin >> a;
findPrimeFactors(a);
}
for (auto prime : primes)
{
int p = prime.first, a = prime.second;
LL t = 1; // t表示为每一个质因数有多少个序列
while (a --) t = (t * p + 1) % mod; // 秦九韶算法
// 上面等价于(p1^0 + p1^1 + p1^2 +...+ p1^alpha) * (p2^0 + p2^2 + p2^2 +...+ p2^alpha)
res = res * t % mod;
}
cout << res << endl;
return 0;
}