CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
求$\sum_{i=1}^n\sum_{j=i+1}^n\gcd(i,j)$。
解法一：蓝书解法，计算贡献
设$f(n)=\sum_{i=1}^{n-1}\gcd(i,n)$，则所求答案为 f(n)的前缀和。 注意到$\gcd(i,n)=k$的值一定是 n 的约数，按照这个约数进行分类。设满足$\gcd(x,n)=k$的约束有 g(n,i)个，则$f(n)=sum\lbrace i\times g(n,i)|d\mod i==0\rbrace $。 依次计算 f(n)需要枚举每个 n 的约数 i，速度较慢，但是对每个 i 枚举它的倍数 ki 来更新 f(ki)的值，此时速度和普通筛法同阶。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct EulerSieve
{
vector<int> p, m, phi;
EulerSieve(int N) : m(N, 0), phi(N, 0)
{
phi[1] = 1;
for (long long i = 2, k; i < N; ++i)
{
if (!m[i])
p.push_back(m[i] = i), phi[i] = i - 1;
for (int j = 0; j < p.size() && (k = i * p[j]) < N; ++j)
{
phi[k] = phi[i] * p[j];
if ((m[k] = p[j]) == m[i])
break;
phi[k] -= phi[i];
}
}
}
};
struct GCDExtremeII : EulerSieve
{
vector<ll> f;
GCDExtremeII(int N) : EulerSieve(N), f(N)
{
for (int i = 1; i < N; ++i)
{
for (int k = 2; k * i < N; ++k)
f[k * i] += i * phi[k];
f[i] += f[i - 1];
}
}
} g(4e6 + 9);
int main()
{
for (int n; ~scanf("%d", &n) && n;)
printf("%lld\n", g.f[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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct EulerSieve
{
vector<int> p, m, phi;
vector<ll> sum;
EulerSieve(int N) : m(N, 0), phi(N, 0), sum(N, 0)
{
phi[1] = 1;
for (long long i = 2, k; i < N; ++i)
{
if (!m[i])
p.push_back(m[i] = i), phi[i] = i - 1;
for (int j = 0; j < p.size() && (k = i * p[j]) < N; ++j)
{
phi[k] = phi[i] * p[j];
if ((m[k] = p[j]) == m[i])
break;
phi[k] -= phi[i];
}
}
for (int i = 0; i < N; ++i)
sum[i] = sum[i - 1] + phi[i];
}
} e(4e6 + 9);
int main()
{
for (ll n, sum, tmp; ~scanf("%lld", &n) && n;)
{
for (int i = 1, j = sum = 0; i <= n; i = j + 1)
tmp = n / i, sum += tmp * tmp * (e.sum[j = n / tmp] - e.sum[i - 1]);
printf("%lld\n", (sum - (n + 1) * n / 2) / 2);
}
}
解法三：莫比乌斯反演
$ans=\sum_{d=1}^nd\sum_{i=1}^{n/d}\mu(i)[\frac{n}{id}]^2=\sum_{T=1}^n[\frac{n}{T}]^2\sum_{d|T}d\mu(\frac{T}{d})$ 数论分块可$O(\sqrt n)$查询，总时间复杂度$O(n\sqrt 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct EulerSieve
{
vector<int> p, m, mu, sum; //素数序列，最小素因子，欧拉函数，莫比乌斯函数
EulerSieve(int N) : m(N, 0), mu(N, 0), sum(N, 0)
{
mu[1] = 1; //m[1]=0
for (long long i = 2, k; i < N; ++i) //防i*p[j]爆int
{
if (!m[i])
p.push_back(m[i] = i), mu[i] = -1; //i是素数
for (int j = 0; j < p.size() && (k = i * p[j]) < N; ++j)
{
if ((m[k] = p[j]) == m[i])
{
mu[k] = 0;
break;
}
mu[k] = -mu[i];
}
}
for (int i = 1; i < N; ++i)
sum[i] = sum[i - 1] + mu[i];
}
} e(4e6 + 9);
int main()
{
for (ll n, sum, tmp; ~scanf("%lld", &n) && n;)
{
sum = 0;
for (int i = 1; i <= n; ++i)
for (ll l = 1, r, tmp, m = n / i; l <= m; l = r + 1)
tmp = m / l, sum += i * tmp * tmp * (e.sum[r = m / tmp] - e.sum[l - 1]);
printf("%lld\n", (sum - (n + 1) * n / 2) / 2);
}
}