最小公倍数之和
题目描述：
对于A1，A2…AN，求 ∑ i=1N∑ j=1Nlcm(Ai,Aj)
题解：
莫比乌斯反演，直接强推一波
推导过程我也是一知半解，大体如图 然后预处理f(T)即可
代码：
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
#define maxn 50005
#define rgt register
int N
, M
, cnt
[maxn
], mu
[maxn
], p
[maxn
], tot
, v
[maxn
];
ll s
[maxn
];
ll ans
=0;
int main(){
scanf( "%d", &N
);
for ( rgt
int i
= 1, x
; i
<= N
; ++i
)
scanf( "%d", &x
), ++cnt
[x
], M
= max( M
, x
);
N
= M
, mu
[1] = 1;
for ( rgt
int i
= 2; i
<= N
; ++i
){
if ( !v
[i
] ) p
[++tot
] = i
, mu
[i
] = -1;
for ( rgt
int j
= 1; j
<= tot
&& i
* p
[j
] <= N
; ++j
){
v
[i
* p
[j
]] = 1;
if ( i
% p
[j
] == 0 ){ mu
[i
* p
[j
]] = 0; break; }
else mu
[i
* p
[j
]] = -mu
[i
];
}
}
for ( rgt
int i
= 1; i
<= N
; ++i
)
for ( rgt
int j
= i
; j
<= N
; j
+= i
)
s
[j
] += 1ll * mu
[i
] * i
;
for ( rgt
int T
= 1; T
<= N
; ++T
){
rgt ll
cur(0);
for ( rgt
int i
= 1, I
= N
/ T
; i
<= I
; ++i
) cur
+= 1ll * cnt
[i
* T
] * i
;
ans
+= T
* cur
* cur
* s
[T
];
} printf( "%lld\n", ans
);
return 0;
}
