题意
求(sum_{i=1}^noperatorname{lcm}(i,n))
多测，(Tleq 3cdot 10^5,1leq nleq 10^6)
题解
看这数据范围也能知道是个预处理+(O(1))查询之类的东西
很容易想到的变形：
然后就不会了
其实是要加一层(sum)，这个不看题解是真想不到，不过这可能是个挺套路的东西？
虽然看起来比较废话但很关键
然后再变形，中括号里除以(d)变成(gcd(dfrac{i}{d},dfrac{n}{d})=1)，其实就是如果(dfrac{i}{d})和(dfrac{n}{d})互质，那么他们都乘(d)以后的(gcd)就是(d)
然后让(i)替代(dfrac{i}{d})
又因为这个(dfrac{n}{d},d)是(n)的“一对”因数，所以这个式子可以直接写成一个更好看的形式：
然后这就有点欧拉(varphi)函数的意思了
关键是那个(i)很碍眼，所以当然是要再看一波题解
由于(gcd(i,d)=gcd(d-i,d))
这个和欧几里得法求(gcd)很像，具体证明可以去这里看
所以考虑(sum_{i=1}^{d}icdot[gcd(i,d)=1])里的每一个(i)和(d-i)，如果(gcd(i,d)
eq 1)肯定就不用管，如果等于(1)，那么这两项的值就是(d)
那么有多少对(gcd(i,d)=gcd(d-i,d)=1)？肯定是(dfrac{varphi(d)}{2})，注意这里说的是多少对
但是很容易发现，(d=1)是上面式子成(0)了，不成立，所以应该给(sum)中的分子加上(1)然后下取整，就避免了这个情况
然后更准确的答案就表述为：
其实这时已经可以(O(sqrt n))回答了，但还可以做的更好
(O(nlog log n))跑一个类似于埃氏筛的过程，我们设(f_j=sum_{d|j}lfloordfrac{varphi(d)cdot d+1}{2}
floor)，应该都知道埃氏筛里面(j)一般代表啥吧
然后对于每一个枚举到的(i)，实际上就是上式中的每一个(d)，然后按公式给(f_j)加上就好
小总结
当然我做的题太少可能说的不全
其实这种(gcd,operatorname{lcm})有关的问题，很多都是转变成([gcd=cdots] imes cdots)的形式，(cdots)都是数，然后和(varphi)结合起来
有时这个转换的方式就是通过加上一个(sum_{d|n})，其它的还没遇见，遇见了可能会写在这里
反正(gcd)这种最容易联想到的就是(varphi)了
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
int n=1e6;
LL phi[1000006],f[1000006];
int prime[500006],notprime[1000006];
inline void get_phi(){
phi[1]=1;
for(reg int i=2;i<=n;i++){
if(!notprime[i]) prime[++prime[0]]=i,phi[i]=i-1;
for(reg int j=1;j<=prime[0]&&i*prime[j]<=n;j++){
notprime[i*prime[j]]=1;
if(!(i%prime[j])){
phi[i*prime[j]]=prime[j]*phi[i];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
int main(){
get_phi();
for(reg int i=1;i<=n;i++)
for(reg int j=i;j<=n;j+=i)
f[j]+=(phi[i]*i+1)>>1;//要加1，如果i=1的话式子就是1了符合要求，如果不是和没加一样不用管
int T=read();while(T--){
n=read();
std::printf("%lld
",f[n]*n);
}
return 0;
}