AcWing 870. 约数个数(数学公式)

题目链接 ： 点击查看

题目描述 ：

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

输入输出格式 ：

输入

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

输出

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

输入输出样例 ：

输入

3
2
6
8

输出

12

题目分析 ：

求约数的个数，只需要需要在程序实现下述公式即可。

核心公式代码实现 ：

for (auto t : primes)  //primes为unordered_map类型
     res = res * (t.second + 1) % mod;

详见如下代码。

代码 ：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#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<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] ++ ;//质因数大于sqrt(n)的情况 
	 }
	 LL res = 1;
	 for (auto p : primes) {
         res = res * (p.second + 1) % mod;
	 }
	 cout << res << endl;
	 return 0;	
} 

---

下面我们给出求约数个数的数学公式

如果 N = p1^c1 * p2^c2 * … *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * … * (ck + 1)