题目描述
给定 n 个正整数 ai,请你输出这些数的乘积的约数之和,答案对 109+7 取模。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个整数 ai。
输出格式
输出一个整数,表示所给正整数的乘积的约数之和,答案需对 109+7 取模。
数据范围
1≤n≤100,
1≤ai≤2×109
样例
输入样例:
3
2
6
8
输出样例:
252
算法1
本题要求求出一个数的所有的因数的和。
依然使用试除法求出数的所有质因数和次数。
求因数和的核心原理
因此我们只需要分别求出A、B....N这些部分的乘积即可。
形如A的多项式的算法
C++ 代码
#include <iostream>
#include <unordered_map>
using namespace std;
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]++;
}
long long result = 1;
for(auto prime:primes){
long long a = prime.first;
long long b = prime.second;
long long sum = 1;
while(b--){
sum = (sum*a+1)%mod;
}
result = result*sum%mod;
}
cout<<result;
}