目录
题目:
分析:
代码:
题目:
给定 n 个正整数 ai,请你输出这些数的乘积的约数之和,答案对 10^9+7 取模。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个整数 ai。
输出格式
输出一个整数,表示所给正整数的乘积的约数之和,答案需对 10^9+7 取模。
数据范围
1≤n≤100,
1≤ai≤2×10^9时/空限制
1s / 64MB
输入样例:
3 2 6 8
输出样例:
252
分析:
见另一篇文章: AcWing--870.约数个数-CSDN博客
代码:
// 假设一个数N=p1^a1·p2^a2···pk^ak(p为质数)
// 公式一:N的约数个数=(a1+1)(a2+1)···(ak+1)个
// 公式二:N的约数之和=(p1^0+p1^2+···+p1^a1)·(p2^0+p2^1+···+p2^a2)···(pk^0+pk^1+···+pk^ak)
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>using namespace std;typedef long long LL;const int N = 110, 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;// 公式二:N的约数之和=(p1^0+p1^2+···+p1^a1)·(p2^0+p2^1+···+p2^a2)···(pk^0+pk^1+···+pk^ak)for (auto p : primes){LL a = p.first, b = p.second; // a为质因数(对应公式中的底数p),b为该质因数的个数(对应公式中的指数a)LL t = 1;// 求(pi^0+pi^2+···+pi^ai),数学问题hhwhile (b -- ) t = (t * a + 1) % mod; // 第一次:t=(1*a+1)=a+1。第二次:t=((a+1)*a+1)=a^2+a+1。第三次:t=((a^2+a+1)*a+1)=a^3+a^2+a+1...第i次:t=a^i+...+a^2+a+1res = res * t % mod;}cout << res << endl;return 0;
}