Description
Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.
Input
The first line contains T the number of test cases. Each of the next T lines contain an integer n.
Output
Output T lines, one for each test case, containing the required sum.
Sample Input
3
1
2
5
1
2
5
Sample Output
1
4
55
4
55
HINT
Constraints
1 <= T <= 300000
1 <= n <= 1000000
Solution
$\sum_{i=1}^{n}lcm(i,n)$
$=\sum_{i=1}^{n}\frac{i\times n}{gcd(i,n)}$
$=\frac{1}{2}(\sum_{i=1}^{n-1}\frac{i\times n}{gcd(i,n)}+\sum_{i=n-1}^{1}\frac{i\times n}{gcd(i,n)})+n$
因为$gcd(a,b)=gcd(a-b,b)$，所以上面的两个$\sum$可以合起来。
$=\frac{1}{2}\sum_{i=1}^{n-1}\frac{n^2}{gcd(i,n)}+n$
设$gcd(i,n)=d$，把式子改为枚举$d$,那么与$n$的$gcd$为$d$的数有$φ(\frac{n}{d})$个。
$=\frac{1}{2}\sum_{d|n}\frac{n^2\times φ(\frac{n}{d})}{d}+n$
设$d'=\frac{n}{d}$，上下约分一下
$=\frac{1}{2}\sum_{d'|n}d'\times φ(d')+n$
预处理出$φ$数组，然后枚举每一个约数去计算它对它所有倍数的贡献，复杂度是调和级数的$O(nlogn)$。
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#define N (1000009)
#define MAX (1000000)
#define LL long long
using namespace std; inline int read()
{
int x=,w=; char c=getchar();
while (c<'' || c>'') {if (c=='-') w=-; c=getchar();}
while (c>='' && c<='') x=x*+c-'', c=getchar();
return x*w;
} LL T,n,cnt,phi[N],ans[N],vis[N],prime[N]; void Preprocess()
{
phi[]=;
for (int i=; i<=MAX; ++i)
{
if (!vis[i]) prime[++cnt]=i, phi[i]=i-;
for (int j=; j<=cnt && i*prime[j]<=MAX; ++j)
{
vis[i*prime[j]]=;
if (i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-);
else {phi[i*prime[j]]=phi[i]*prime[j]; break;}
}
}
for (int i=; i<=MAX; ++i)
for (int j=i; j<=MAX; j+=i)
ans[j]+=i*phi[i]/;
for (int i=; i<=MAX; ++i) ans[i]=ans[i]*i+i;
} int main()
{
Preprocess();
T=read();
while (T--) n=read(), printf("%lld\n",ans[n]);
}