Madoka and The Best University
原题链接
题意
给你一个整数 \(n\)，求解 \(\sum_{a+b+c=n}\operatorname{lcm}(c,\gcd(a,b))\)。
⭐rating: 2200
分析
枚举 \(t=\gcd(a,b)\)，因此原式等于 \(\sum\operatorname{lcm}(c,t)\sum_{a+b=n-c}[\gcd(a,b)=t]\)。
如果 \(\gcd(a,b)=t\)，那么 \(\dfrac{a}{t},\dfrac{b}{t}\) 互质。并且 \(\gcd(a,b)=\gcd(a,a+b)=\gcd(a,n-c)\)，即求满足 \(\dfrac{a}{t},\dfrac{n-c}{t}\) 互质的个数，因为 \(n-c=a+b>a\)，所以就是求 \(\phi(\dfrac{n-c}{t})\)。
因此答案为 \(\sum\operatorname{lcm}(c,t)\times\phi(\dfrac{a+b}{t})\)，其中 \(t\) 为 \(a+b\) 的因子。
时间复杂度为 \(O(n\log^{2}n)\)
代码
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 | #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 lcm(int a, int b) {
return (i64)a * b / std::__gcd(a, b);
}
int main() {
int n;
std::cin >> n;
std::vector<int> phi(n + 1);
std::iota(phi.begin(), phi.end(), 0);
for (int i = 1; i <= n; i++) {
for (int j = 2 * i; j <= n; j += i) {
phi[j] -= phi[i];
}
}
Z res = 0;
for (int t = 1; t <= n - 2; t++) {
for (int s = t * 2; s <= n; s += t) {
int c = n - s;
res += lcm(c, t) * Z(phi[s / t]);
}
}
std::cout << res << '\n';
return 0;
}
|