公约数的和
简单的小容斥。
$$
\begin{aligned}
& \sum_{i=1}^{n}\sum_{j=i+1}^{n}\gcd(i,j)
\\
=& \dfrac{1}{2}\left(\sum_{i=1}^{n}\sum_{j=1}^{n}\gcd(i,j)-\sum_{i=1}^{n}i\right)
\\
=& \dfrac{1}{2}\left(\sum_{k=1}\varphi(k)\left\lfloor\dfrac{n}{k}\right\rfloor^2-\sum_{i=1}^{n}i\right)
\end{aligned}
$$
数论分块就行了。
答案可能有些大，反正开 __int128 就没事了。
时间复杂度 $O(n)$。
比较闲的话可以上杜教筛 $O(n^{2/3})$。
代码：
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
| #include<iostream>
#include<cstdio>
#define ll __int128
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
const ll N=2e6;
ll n,cnt;
ll prime[N+5],phi[N+5],sphi[N+5];
bool f[N+5];
inline ll F(ll x) {return x*(x+1)/2;}
inline void Init() {
f[1]=1;phi[1]=1;
for(ll i=2;i<=n;i++) {
if(!f[i]) {prime[++cnt]=i;phi[i]=i-1;}
for(ll j=1;j<=cnt&&i*prime[j]<=n;j++) {
f[i*prime[j]]=1;
if(i%prime[j]==0) {
phi[i*prime[j]]=phi[i]*prime[j];break;
}
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
for(ll i=1;i<=n;i++) sphi[i]=sphi[i-1]+phi[i];
}
int main() {
n=read();Init();
ll ans=0;
for(ll i=1,j;i<=n;i=j+1) {
j=n/(n/i);ans=ans+(sphi[j]-sphi[i-1])*(n/i)*(n/i);
}
ans-=F(n);ans/=2;
write(ans);
return 0;
}
|