P3327-[SDOI2015]约数个数和
题目:
题目描述:
设 $d(x)$ 为 $x$ 的约数个数，给定 $n,m$，求
$$\sum_{i=1}^n\sum_{j=1}^md(ij)$$
输入格式:
输入文件包含多组测试数据。
第一行，一个整数 $T$，表示测试数据的组数。
接下来的 $T$ 行，每行两个整数 $n,m$。
输出格式:
$T$ 行，每行一个整数，表示你所求的答案。
样例:
样例输入 1:
样例输出 1:
思路:
首先给出一个公式：
$$d(ij)=\sum\limits_{x\mid i}\sum\limits_{y\mid j} [\gcd(x,y)=1]$$
因此所求为
$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x\mid i}\sum\limits_{y\mid j} [\gcd(x,y)=1]$$
改变求和顺序，先枚举因数 $x$ 和 $y$
$$\sum\limits_{x=1}^n\sum\limits_{y=1}^m \left\lfloor\frac{n}{x}\right\rfloor \left\lfloor\frac{m}{y}\right\rfloor [\gcd(x,y)=1]$$
将 $x,y$ 换成 $i,j$ 吧 QAQ
$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor[\gcd(i,j)=1]$$
开始莫比乌斯反演！设
$$f(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor[\gcd(i,j)=x]$$
$$g(x)=\sum_{x\mid d} f(d)$$
则有
$$g(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor[x\mid\gcd(i,j)]$$
我们把 $x$ 提出就可以消除 $\gcd$ 的影响
$$g(x)=\sum\limits_{i=1}^{\frac{n}{x}}\sum\limits_{j=1}^{\frac{m}{x}} \left\lfloor\frac{n}{ix}\right\rfloor \left\lfloor\frac{m}{jx}\right\rfloor$$
再根据 $f(x)$ 的定义，得到答案为 $f(1)$
又因为
$$f(n)=\sum\limits_{n\mid d}\mu(\frac{d}{n})g(d)$$
故
$$f(1)=\sum\limits_{1\mid d}\mu(\frac{d}{1})g(d)=\sum_{i=1}^n \mu(i)g(i)$$
接下来再考虑如何求 $g(x)$，我们可以先计算 $s(x)=\sum\limits_{i=1}^{x} \left\lfloor\frac{x}{i}\right\rfloor$，就可以 $\Theta(1)$ 计算 $g(x)$。
时间复杂度：$\Theta(T\sqrt{n})$
如何证明 Solution 中的公式？
$$d(ij)=\sum\limits_{x\mid i}\sum\limits_{y\mid j} [\gcd(x,y)=1]$$
我们考虑把每个因子一一映射。
如果 $ij$ 的因子 $k$ 中有一个因子 $p^c$，$i$ 中有因子 $p^a$，$j$ 中有因子 $p^b$。我们规定：
- 如果 $c\leqslant a$，那么在 $i$ 中选择。
- 如果 $c>a$，那么我们把 $c$ 减去 $a$，在 $j$ 中选择 $p^{c-a}$（在 $j$ 中选择 $p^e$ 表示的是 $p^{a+e}$）
对于 $ij$ 的因子 $k$ 的其他因子同理。于是对于任何一个 $k$ 有一个唯一的映射，且每一个选择对应着唯一的 $k$。
通过如上过程，我们发现：对于 $ij$ 的因子 $k=\prod {p_i}^{c_i}$，我们不可能同时在 $i$ 和 $j$ 中选择 $p_i$（优先在 $i$ 中选择，如果不够就只在 $j$ 中选择不够的指数），故 $x$ 和 $y$ 必须互质。
等式得证。
实现:
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
// Problem : P3327 [SDOI2015]约数个数和
// Contest : Luogu
// URL : https://www.luogu.com.cn/problem/P3327
// Memory Limit : 125 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
/*
*User: $%U%$
*Time: $%Y%$.$%M%$.$%D%$ $%h%$:$%m%$:$%s%$
*/
#include <bits/stdc++.h>
using namespace std;
#ifndef use_ios11
#define use_ios11
using namespace std;
struct ins
{
int ans;
ins() { ans = 1; }
#define endl '\n'
void read()
{
}
void read1(char &s)
{
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
s = c;
if (c == EOF)
ans = 0;
}
void read1(string &s)
{
s = "";
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
for (; isprint(c) && c != ' ' && c != '\n' && c != '\t'; c = getchar())
s += c;
if (c == EOF)
ans = 0;
}
template <typename T>
void read1(T &n)
{
T x = 0;
int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
{
if (c == '-')
f = -1;
if (c == EOF)
{
ans = 0;
return;
}
}
for (; isdigit(c); c = getchar())
x = x * 10 + c - 48;
n = x * f;
if (c == EOF)
ans = 0;
if (c != '.')
return;
T l = 0.1;
while ((c = getchar()) <= '9' && c >= '0')
x = x + (c & 15) * l, l *= 0.1;
n = x * f;
if (c == EOF)
ans = 0;
}
void write() {}
void write1(string s)
{
int n = s.size();
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(const char *s)
{
int n = strlen(s);
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(char s) { putchar(s); }
void write1(float s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%df", x);
printf(y, s);
}
void write1(double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dlf", x);
printf(y, s);
}
void write1(long double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dLf", x);
printf(y, s);
}
template <typename T>
void write1(T n)
{
if (n < 0)
n = -n, putchar('-');
if (n > 9)
write1(n / 10);
putchar('0' + n % 10);
}
template <typename T>
friend ins operator>>(ins x, T &n);
template <typename T>
friend ins operator<<(ins x, T n);
operator bool() { return ans; }
};
template <typename T>
ins operator>>(ins x, T &n)
{
if (!x.ans)
return x;
x.read1(n);
return x;
}
template <typename T>
ins operator<<(ins x, T n)
{
x.write1(n);
return x;
}
ins yin;
ins yout;
#endif
const int maxn = 5e4 + 100;
int mu[maxn], s[maxn], flg[maxn], tot, p[maxn];
void pre()
{
mu[1] = 1;
for (int i = 2; i <= 5e4; ++i)
{
if (!flg[i])
p[++tot] = i, mu[i] = -1;
for (int j = 1; j <= tot && i * p[j] <= 5e4; ++j)
{
flg[i * p[j]] = 1;
if (i % p[j] == 0)
{
mu[i * p[j]] = 0;
break;
}
else
{
mu[i * p[j]] = -mu[i];
}
}
}
for (int i = 1; i <= 5e4; ++i)
mu[i] += mu[i - 1];
for (int x = 1; x <= 5e4; ++x)
{
long long res = 0;
for (int i = 1, j; i <= x; i = j + 1)
j = x / (x / i), res += 1LL * (j - i + 1) * (x / i);
s[x] = res;
}
}
int n, m;
int main()
{
pre();
int TTT;
yin >> TTT;
while (TTT--)
{
yin >> n >> m;
if (n > m)
{
swap(n, m);
}
long long ans = 0;
for (int i = 1, j; i <= n; i = j + 1)
{
j = min(n / (n / i), m / (m / i));
ans += 1ll * (mu[j] - mu[i - 1]) * s[n / i] * s[m / i];
}
yout << ans << endl;
}
return 0;
}
|