Problem Statement
求
$$\sum_{i=1}^n \sum_{j=1}^n \gcd(i, j)$$第一行一个整数 $n$。
Output
第一行一个整数表示答案。
Sample Output
Constraints
对于 $30%$ 的数据，$n\leq 3000$。
对于 $60%$ 的数据，$7000\leq n\leq 7100$。
对于 $100%$ 的数据，$n\leq 10^5$。
Solving
我们由欧拉函数的结论可以推出：
$$
\begin{align*} 原式=&\sum_{i = 1}^{n}\sum_{j = 1}^{n}\sum_{d\mid\gcd(i,j)}\varphi(d)\\ =&\sum_{i = 1}^{n}\sum_{j = 1}^{n}\sum_{\substack{d\mid i\\d\mid j}}\varphi(d)\quad \\\ =&\sum_{i = 1}^{n}\sum_{j = 1}^{n}\sum_{d = 1}^{n}\varphi(d)[d\mid i][d\mid j]\quad \\\ =&\sum_{d = 1}^{n}\varphi(d)\sum_{i = 1}^{n}\sum_{j = 1}^{n}[d\mid i][d\mid j]\\ =&\sum_{d = 1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor^{2} \end{align*}
$$
其中对于类似于n / d向下取整的式子，我们还可以利用数论分块的结论，在求出欧拉函数 Phi(x)的前n项和的前提下将答案更新的时间复杂度从O($N$)降至O($\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
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
|
#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f
#define NINF -0x3f3f3f3f
#define Single
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 100005;
const int M = 0;
ll prefix[N];
//欧拉函数线性筛
//---------------------------------------------------
vector<int> pri;
bool not_prime[N];
int phi[N];
void Euler_Phi(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!not_prime[i])
{
pri.push_back(i);
phi[i] = i - 1;
}
for (int pri_j : pri)
{
if (i * pri_j > n) break;
not_prime[i * pri_j] = true;
if (i % pri_j == 0) {
phi[i * pri_j] = phi[i] * pri_j;
break;
}
phi[i * pri_j] = phi[i] * phi[pri_j];
}
}
}
//---------------------------------------------------
signed main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T;
#ifdef Single
T = 1;
#endif
while(T--)
{
int n;
cin >> n;
ll ans = 0;
Euler_Phi(n);
for(int i=1;i<=n;i++) prefix[i] = prefix[i-1] + phi[i];//计算欧拉函数的前缀和
//数论分块计算
for(int l=1,r;l<=n;l=r+1)
{
r = n / (n/l);
ans += (prefix[r]-prefix[l-1]) * (n/l) * (n/l) * (1LL);//不要忘记LL类型转换
}
cout << ans << endl;
}
return 0;
}
|