永恒守候的爱恋
原题链接
TAG：因子数公式，数学，模运算
思路
若 \(n\) 的质因数分解形式为 \(𝑛=𝑝_1^{𝑎_1}∗𝑝_2^{𝑎_2}∗...∗𝑝_𝑘^{𝑎_𝑘}\)。
那么 \(n\) 的因子数量为 \((a_1+1)*(a_2+1)*...*(a_k+1)\)。
证明如下，对于每个素因子 \(p_i\) 而言，可以取 \(0\) 个、取 \(1\) 个……取 \(a_i\)个，共有 \(a_i+1\) 种取法。根据乘法原理，总方案数为 \(\sum_{i=1}^{k}(a_i+1)\)
根据这个性质，我们可以想出这样的策略：首先每个素数第一次出现依次排下来，然后还有次数的素数的第二次依次排下来……以此类推。这样一定是最优的。因为当素数的出现次数从 \(i\) 次变成 \(i+1\) 次的时候，带来的贡献为 \(\frac{𝑖+2}{𝑖+1}\)；（之前是乘以 \(i+1\)，现在是乘以 \(i+2\)）。所以每次优先选择“目前已选择的出现次数最少的素数”是更优的。
这样当我们选择出现次数为 \(i\) 的素数时，前缀因子数量从此时开始即为一个公比为 \(\frac{𝑖+2}{𝑖+1}\) 的等比数列；我们可以通过等比数列求和公式快速算出这一段的和。这样总复杂度即为 \(O(n\log{n})\)，其中log是快速幂/逆元部分的复杂度。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118 | #include <bits/stdc++.h>
using i64 = long long;
const int P = 1e9 + 7;
// assume -P <= x < 2P
int norm(int x) {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
template<class T>
T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Z {
int x;
Z(int x = 0) : x(norm(x)) {}
Z(i64 x) : x(norm(x % P)) {}
int val() const {
return x;
}
Z operator-() const {
return Z(norm(P - x));
}
Z inv() const {
assert(x != 0);
return power(*this, P - 2);
}
Z &operator*=(const Z &rhs) {
x = i64(x) * rhs.x % P;
return *this;
}
Z &operator+=(const Z &rhs) {
x = norm(x + rhs.x);
return *this;
}
Z &operator-=(const Z &rhs) {
x = norm(x - rhs.x);
return *this;
}
Z &operator/=(const Z &rhs) {
return *this *= rhs.inv();
}
friend Z operator*(const Z &lhs, const Z &rhs) {
Z res = lhs;
res *= rhs;
return res;
}
friend Z operator+(const Z &lhs, const Z &rhs) {
Z res = lhs;
res += rhs;
return res;
}
friend Z operator-(const Z &lhs, const Z &rhs) {
Z res = lhs;
res -= rhs;
return res;
}
friend Z operator/(const Z &lhs, const Z &rhs) {
Z res = lhs;
res /= rhs;
return res;
}
friend std::istream &operator>>(std::istream &is, Z &a) {
i64 v;
is >> v;
a = Z(v);
return is;
}
friend std::ostream &operator<<(std::ostream &os, const Z &a) {
return os << a.val();
}
};
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int n;
std::cin >> n;
std::vector<int> a(n);
int max = 0;
for (int i = 0; i < n; i++) {
std::cin >> a[i];
max = std::max(max, a[i]);
}
std::vector<int> c(max + 1);
for (int i = 0; i < n; i++) {
c[a[i]]++;
}
for (int i = max - 1; i; i--) {
c[i] += c[i + 1];
}
Z ans = 0, a1 = 1;
for (int i = 1; i <= max; i++) {
Z q = Z(i + 1) / i;
Z qn = power(q, c[i]);
ans += a1 * q * (1 - qn) / (1 - q);
a1 *= qn;
}
std::cout << ans << "\n";
return 0;
}
|