题目要我们求这个：
[sum_{i=1}^n lcm(i,n)
]
开始化式子：
[sum_{i=1}^{n} frac{i*n}{gcd(i,n)}
]
[sum_{d|n} sum_{i=1}^{frac{n}{d}} i*n[gcd(i,frac{n}{d})=1]
]
[n*sum_{d|n}sum_{i=1}^{d}i[gcd(i,d)=1]
]
注意那个(sum_{i=1}^{d}i[gcd(i,d)=1])是求([1,d])中所有与(d)互质的数的和，可以证明当(d>1)时，它等于(frac{d*phi(d)}{2})，证明如下：
对于每个(i)，若它与(d)互质，则(d-i)也与(d)互质，每一对(i)与(d-i)的和为(d)，所以平均每个与(d)互质的数的值为(frac{d}{2})，一共有(phi(d))个与(d)互质的数，所以他们的和为(frac{d*phi(d)}{2})
而与(1)互质的数的和显然为(1)
所以上式可化为
[n*ig((sum_{d|n,d>1}frac{d*phi(d)}{2})+1ig)
]
[ig( frac{n}{2}*sum_{d|n,d>1}d*phi(d)ig)+n
]
设(g(n)=sum_{d|n}d*phi(d))，上式化为：
[frac{n}{2}*(g(n)-1)+n
]
其中(g(n))是一个积性函数，可以(O(n))筛出
每次询问是(O(1))的
总时间复杂度为(O(n+T))
关于如何线筛出(g(n))：
(n)为质数：(g(n)=1+n*phi(n)=1+n*(n-1))
(n=p^k)：
[g(n)=1+sum_{i=1}^{k}p^i*phi(p^i)
]
[=1+sum_{i=1}^{k}p^i*p^{i-1}*(p-1)
]
[=1+(p-1)sum_{i=1}^{k}p^{2i-1}
]
[=1+(p-1)frac{p^{2k+1}-p}{p^2-1}
]
[=1+frac{p^{2k+1}-p}{p+1}
]
(n)的最小质因子为(p)：(g(n)=g(n'*p^k)=g(n')*g(p^k))
然后就可以线性筛了
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 1000007
#define ll long long
const int lim=1e6;
int pr[N],cnt,pk[N];
bool zhi[N];
ll f[N];
void Init()
{
int i,j;
f[1]=1;
for(i=2;i<=lim;i++)
{
if(!zhi[i])
{
pr[++cnt]=i,f[i]=1+1ll*i*(i-1);
pk[i]=i;
}
for(j=1;j<=cnt&&i*pr[j]<=lim;j++)
{
int p=pr[j],x=i*p;
zhi[x]=true;
if(i%p==0)
{
pk[x]=pk[i]*p;
f[x]=f[x/pk[x]]*(1+(1ll*pk[x]*pk[x]*p-p)/(p+1));
break;
}
pk[x]=p;
f[x]=f[i]*f[p];
}
}
for(i=1;i<=lim;i++)
f[i]=1ll*(f[i]-1)*i/2+i;
}
int main()
{
int t,n;
Init();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%lld
",f[n]);
}
return 0;
}
我原本的做法是用(mu)暴力拆([gcd(i,d)=1])，但是那样做的复杂度是(O(nlog n))的，也没有这个做法巧妙，这里就不讲了。