You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2.0 KiB
2.0 KiB
一、题目描述
给定 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
二、约数个数公式
如果n的唯一分解式： \LARGE n={p_1}^{r_1}\cdot {p_2}^{r_2} \cdot ... \cdot {p_k}^{r_k}
n的约数个数公式：
\large d(n) = (r_1+1) \cdot (r_2+1) \cdot ... \cdot (r_k+1)证明
以p_1为例，这个质数因子，可以选择0个，可以选择1个，...,最多可以选择r_1个，就是有r_1+1种选择的可能性，其它p_2,p_3,...,p_k都是如此，根据乘法原理，所有的可能性就是(r_1+1) \cdot (r_2+1) \cdot ... \cdot (r_k+1)。
举个栗子：
180= 2^2 * 3^2 * 5
约数个数=(1+2) * (1+2) * (1+1) =18
三、求数字连乘积的约数个数
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
const int N = 110;
const int MOD = 1e9 + 7;
unordered_map<int, int> primes;
int n;
signed main() {
cin >> n;
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]++;
}
int res = 1;
for (auto p : primes) res = res * (p.second + 1) % MOD;
printf("%lld\n", res);
}
四、求单个数字的约数个数
求连乘积的都会了的话，这个就简单了，不就是n=1时的情况吗？不多说了~