【AcWing】871. 约数之和
分解完质因数后，直接代入求和公式。
#include<iostream>
#include<algorithm>
#include<unordered_map>
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]++;//大于sqrt(x)的质因数
}
LL res=1;
for(auto prime:primes){
int p=prime.first,a=prime.second;//p是底数，a是指数
LL t=1;
while(a--){//乘指数次
t=(t*p+1)%mod;//求每一个p的和
}
res=res*t%mod;//相乘
}
cout<<res<<endl;
return 0;
}