AcWing 871. 约数之和
原题链接
简单
作者:
lxmydx
,
2024-03-30 18:34:15
,
所有人可见
,
阅读 2
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
int main()
{
int n;
cin>>n;
unordered_map<int,int> primes;
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]++;
}
LL res = 1;
for(auto p : primes)
{
LL a = p.first, b = p.second;
LL t = 1;
//对每个底数算总的结果时就可能溢出,然后把这些结果乘起来的时候还可能溢出
//所以每次都取模,保证结果不溢出
while(b--) t = (t*a+1)%mod;//这里是计算 p0一直加到p的k的次方 的和,可以手动模拟一遍就看出来了
res = res * t % mod;//套用约束之和的公式
}
cout<<res<<endl;
return 0;
}