数论经典问题——约数之和

给定 n个正整数 ai，请你输出这些数的乘积的约数之和，答案对 1e9+7取模

第一行包含整数 n。

接下来 n 行，每行包含一个整数 ai。

输出格式

输出一个整数，表示所给正整数的乘积的约数之和，答案需对 1e9+7取模。

数据范围

1≤n≤100
1≤ai≤2×1e9

输入样例：

3
2
6
8

输出样例：

252

根据算数基本定理，一个合数可以分解成质数的乘积

形如：x = p1^a1*p2^a2.....*pk^ak;

其中，pk为x的质因子，ak为质因子的指数

则根据乘法原理，可以看出此合数的约数个数共有（a1+1）*（a2+1）....*(ak+1)

约数之和则有(p1^0+p1^1....+p1^a1)*(p2^0+p2^1....+p2^a2)....*(pk^0+pk^1...+pk^ak)

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;const int N = 110;
typedef long long LL;int main(void)
{int t;cin >> t;// 建立一个哈希表用来存储质因子的指数 unordered_map<int,int> primes;while(t--){int x;cin >> x;for(int i=2;i<=x/i;i++){// 使用试除法得出每一个质因子的指数 if(x%i==0) primes[i]++;}if(x>1) primes[x]++;}LL res= 1;for(auto prime:primes){int p = prime.first,a = prime.second;LL t = 1;// 当t=1时，原式=p+1;// 当t=2时，原式=p^2+p+1;// 这一步是为了得出括号中的每一项 while(a--) t = (t*p+1)%MOD;// 最后将这些所有项全部乘起来 res = res*t%MOD;}cout << res <<endl;return 0;
}

希望对你有所帮助！