一个数的约数个数是多少，AcWing 870题教你快速求解？
- 内容介绍
- 文章标签
- 相关推荐
本文共计592个文字，预计阅读时间需要3分钟。
题目：给定$n$个正整数$a_i$，请你输出这些数的乘积的约数个数，答案对$10^9+7$取模。
输入格式：第一行包含一个整数$n$。接下来$n$行，每行包含一个整数$a_i$。
输出格式：输出一个整数，表示乘积的约数个数。
样例输入：
42
34
5
样例输出：
32
题目
给定 $n$ 个正整数 $a_i$，请你输出这些数的乘积的约数个数，答案对 $10^9+7$ 取模。
输入格式 第一行包含整数 $n$。
接下来 $n$ 行，每行包含一个整数 $a_i$。
输出格式 输出一个整数，表示所给正整数的乘积的约数个数，答案需对 $10^9+7$ 取模。
数据范围 $1≤n≤100,1≤a_i≤2×10^9$ 输入样例：
3
2
6
8
输出样例：
12
思路
约数个数定理： 对于一个大于1正整数n可以分解质因数： $n = {p_1}^{a_1}{p_2}^{a_2}...*{p_k}^{a_k}$ 则 $n$ 的正约数的个数就是 $sum = (a_1 + 1) * (a_2 + 1) * ... * (a_k + 1)$。 其中 $a1、a2、a3…ak$ 是 $p1、p2、p3，…pk$ 的指数。
定理简证 首先同上，$n$ 可以分解质因数：$n = {p_1}^{a_1}{p_2}^{a_2}...*{p_k}^{a_k}$, 由约数定义可知 ${p_1}^{a_1}$ 约数有: $p_1^0, p_1^1, p_1^2, ...$，共（$a_1+1$）个；同理 ${p_2}^{a_2}$ 的约数有 $(a_2+1)$ 个；……；${p_k}^{a_k}$ 的约数有 $(a_k+1)$ 个。 故根据乘法原理：$n$ 的约数的个数就是 $(a_1+1)(a_2+1)(a_3+1)…(a_k+1)$。
本题中，我们通过试除法求出每个约数最大个数，即上述公式中的指数，将结果按公式计算即可。
代码
#include <iostream>
#include <unordered_map>
typedef long long LL;
using namespace std;
const int mod = 1e9 + 7;
int n;
int main()
{
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;
for (auto p: primes) res = res * (p.second + 1) % mod;
cout << res << endl;
return 0;
}
本文共计592个文字，预计阅读时间需要3分钟。
题目：给定$n$个正整数$a_i$，请你输出这些数的乘积的约数个数，答案对$10^9+7$取模。
输入格式：第一行包含一个整数$n$。接下来$n$行，每行包含一个整数$a_i$。
输出格式：输出一个整数，表示乘积的约数个数。
样例输入：
42
34
5
样例输出：
32
题目
给定 $n$ 个正整数 $a_i$，请你输出这些数的乘积的约数个数，答案对 $10^9+7$ 取模。
输入格式 第一行包含整数 $n$。
接下来 $n$ 行，每行包含一个整数 $a_i$。
输出格式 输出一个整数，表示所给正整数的乘积的约数个数，答案需对 $10^9+7$ 取模。
数据范围 $1≤n≤100,1≤a_i≤2×10^9$ 输入样例：
3
2
6
8
输出样例：
12
思路
约数个数定理： 对于一个大于1正整数n可以分解质因数： $n = {p_1}^{a_1}{p_2}^{a_2}...*{p_k}^{a_k}$ 则 $n$ 的正约数的个数就是 $sum = (a_1 + 1) * (a_2 + 1) * ... * (a_k + 1)$。 其中 $a1、a2、a3…ak$ 是 $p1、p2、p3，…pk$ 的指数。
定理简证 首先同上，$n$ 可以分解质因数：$n = {p_1}^{a_1}{p_2}^{a_2}...*{p_k}^{a_k}$, 由约数定义可知 ${p_1}^{a_1}$ 约数有: $p_1^0, p_1^1, p_1^2, ...$，共（$a_1+1$）个；同理 ${p_2}^{a_2}$ 的约数有 $(a_2+1)$ 个；……；${p_k}^{a_k}$ 的约数有 $(a_k+1)$ 个。 故根据乘法原理：$n$ 的约数的个数就是 $(a_1+1)(a_2+1)(a_3+1)…(a_k+1)$。
本题中，我们通过试除法求出每个约数最大个数，即上述公式中的指数，将结果按公式计算即可。
代码
#include <iostream>
#include <unordered_map>
typedef long long LL;
using namespace std;
const int mod = 1e9 + 7;
int n;
int main()
{
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;
for (auto p: primes) res = res * (p.second + 1) % mod;
cout << res << endl;
return 0;
}