loj6375题解

好久没怎么做题了,做道水题练练手.

$$\begin{aligned}&\sum\mathrm{lcm}(i,n)\\=&n\sum\frac{i}{\gcd(i,n)}\\=&n\sum _{d|n}\frac{1}{d}\sum _{i=1}^{n/d}di[\gcd(i,n/d)=1]\end{aligned}$$

记$f(n)=\sum _{i=1}^ni[\gcd(i,n)=1]$,那么当$n>1$的时候均有$f(n)=\frac{n\varphi(n)}{2}$,而答案即为$n\sum _{d|n}f(\frac{n}{d})$.

预处理欧拉函数就可以了.

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ele long long
using namespace std;
#define maxn 1000010
ele n,pcnt,plst[maxn],phi[maxn];
bool flag[maxn];
inline ele f(ele n){
return n==1?1:n*phi[n]/2;
}
int main(){
freopen("lcm.in","r",stdin); freopen("lcm.out","w",stdout);
pcnt=0; phi[1]=1;
memset(flag,0,sizeof(flag));
for (int i=2; i<maxn; ++i){
if (!flag[i]) plst[pcnt++]=i,phi[i]=i-1;
for (int j=0; j<pcnt && i*plst[j]<maxn; ++j){
flag[i*plst[j]]=true;
if (i%plst[j]) phi[i*plst[j]]=phi[i]*phi[plst[j]];
else{
phi[i*plst[j]]=phi[i]*plst[j];
break;
}
}
}
ele T;
scanf("%lld",&T);
while (T--){
scanf("%lld",&n);
ele ans=0;
for (ele d=1; d*d<=n; ++d)
if (n%d==0){
ans+=f(n/d);
if (d*d!=n) ans+=f(d);
}
printf("%lld\n",ans*n);
}
return 0;
}