AcWing--870.约数个数
目录
题目:
分析:
代码:
题目:
给定 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
输出样例:
12
分析:
假设一个数 N=p1^a1·p2^a2···pk^ak(p为质数)......①
N 的任意一个约数 a=p1^b1·p2^b2···pk^bk(其中 0<=bi<=ai)......②
即 N 的任意一个约数都可以用②这种形式表示,而每一个bi的取值范围都在 0~ai 之间,并且N的任意两个约数之间,只要有一个 bi 不相同,那么这两个约数就不相同(算法基本定理)
因为 bi 的取值共有 0~ai 共 (ai+1) 个取值
所以
公式一:
N的约数个数= (a1+1)(a2+1)···(ak+1) 个
ps:int 范围内的数的约数个数最多为1500个左右。
拓展:同时还可以推出另外一个 公式
公式二:
N的约数之和=(p1^0+p1^2+···+p1^a1)·(p2^0+p2^1+···+p2^a2)···(pk^0+pk^1+···+pk^ak)
自己拆开来看看,就会发现其实就是每个约数的排列组合的和。
代码:
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
// unordered_map 是 C++ 中的一个关联容器,它提供了一种高效的方式来维护一个由键和值组成的集合,其中每个键都是唯一的。这个容器使用哈希表来实现,因此它能够在常数时间内完成查找、插入和删除操作,这使得它比使用红黑树实现的 map 容器在某些情况下更加高效。
unordered_map<int, int> primes; // 用于存这些数的乘积因式分解后的所有底数和指数
// 分别分解每一个数的质因数,再累加,就可得到所有数乘积的质因数的个数
while (n -- )
{
int x;
cin >> x;
// 第一步:分解质因数,即求x的每个质因数的个数。x=p1^a1·p2^a2···pk^ak(例如x=16,16=2*2*2*2=2^4,16由4个质因数2构成,则primes[2]=4,用哈希表存)
for (int i = 2; i <= x / i; i ++ )
while (x % i == 0)
{
x /= i;
primes[i] ++ ;
}
if (x > 1) primes[x] ++ ; // x是质数的情况
}
// 第二步:求约数个数
LL res = 1;
for (auto p : primes) res = res * (p.second + 1) % mod;// 公式一:N的约数个数=(a1+1)(a2+1)···(ak+1)个
cout << res << endl;
return 0;
}