目录
- 1 基础知识
- 2 模板
- 3 工程化
1 基础知识
求一个数x的约数数目和约数之和的关键步骤:
- 对数x分解质约数,
x = p 1 c 1 ⋅ p 2 c 2 ⋯ p k c k x=p_1^{c_1}\cdot p_2^{c_2}\cdots p_k^{c_k} x=p1c1⋅p2c2⋯pkck
unordered_map<int,int> get_prime_divisors(int x) {//对一个数x进行分解质因子操作
unordered_map<int,int> mp;
for (int i = 2; i <= x / i; ++i) {
if (x % i == 0) {
int s = 0;
while (x % i == 0) {
x /= i;
s++;
}
mp[i] = s;
}
}
if (x > 1) mp[x] = 1;
return mp;
}
- 那么约数总数计算如下,
c n t = ( c 1 + 1 ) ( c 2 + 1 ) ⋯ ( c k + 1 ) cnt=(c_1+1)(c_2+1)\cdots(c_k+1) cnt=(c1+1)(c2+1)⋯(ck+1) - 那么约数之和计算如下,
s = ( p 1 0 + p 1 1 + ⋯ + p 1 c 1 ) ( p 2 0 + p 2 1 + ⋯ + p 2 c 2 ) ⋯ ( p k 0 + p k 1 + ⋯ + p k c k ) s=(p_1^0+p_1^1+\cdots+p_1^{c_1})(p_2^0+p_2^1+\cdots + p_2^{c_2})\cdots(p_k^0+p_k^1+\cdots+p_k^{c_k}) s=(p10+p11+⋯+p1c1)(p20+p21+⋯+p2c2)⋯(pk0+pk1+⋯+pkck)
2 模板
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数: (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和: (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
3 工程化
题目1:求一串数的乘积的约数总数。
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
const int mod = 1e9 + 7;
unordered_map<int,int> mp;
void get_prime_divisors(int x) {
//cout << "x = " << x << endl;
for (int i = 2; i <= x / i; ++i) {
if (x % i == 0) {
int s = 0;
while (x % i == 0) {
x /= i;
s++;
}
mp[i] += s;
//cout << "i = " << i << ", s = " << s << endl;
}
}
if (x > 1) {
mp[x] += 1;
//cout << "x = " << x << ", mp[x] = " << mp[x] << endl;
}
return;
}
int main() {
int n;
cin >> n;
while (n--) {
int x;
cin >> x;
get_prime_divisors(x);
}
long long res = 1;
for (auto [x, y] : mp) {
res *= (y + 1);
res %= mod;
}
cout << res << endl;
return 0;
}
题目2:求一串数的约数之和。
#include <iostream>
#include <unordered_map>
using namespace std;
const int mod = 1e9 + 7;
unordered_map<int,int> mp;
void get_prime_divisors(int x) {
for (int i = 2; i <= x / i; ++i) {
if (x % i == 0) {
int s = 0;
while (x % i == 0) {
x /= i;
s++;
}
mp[i] += s;
}
}
if (x > 1) mp[x] += 1;
return;
}
int main() {
int n;
cin >> n;
while (n--) {
int x;
cin >> x;
get_prime_divisors(x);
}
long long res = 1;
for (auto [x, a] : mp) {
//遍历每一个质数x
//cout << "x = " << x << ", a = " << a << endl;
long long t = 1;
while (a--) {
t = (t * x + 1) % mod;
}
res = (res * t) % mod;
}
cout << res << endl;
return 0;
}