P1891 疯狂LCM
suxxsfe
·
·
题解
题意
求\sum_{i=1}^n\operatorname{lcm}(i,n)
多测，T\leq 3\cdot 10^5,1\leq n\leq 10^6
题解
看这数据范围也能知道是个预处理+O(1)查询之类的东西
很容易想到的变形：
\sum_{i=1}^n\operatorname{lcm}(i,n)=\sum_{i=1}^n\frac{i\cdot n}{\gcd(i,n)}=n\sum_{i=1}^n\frac{i}{\gcd(i,n)}
然后就不会了
其实是要加一层\sum，这个不看题解是真想不到，不过这可能是个挺套路的东西？
n\sum_{d | n}\sum_{i=1}^n\frac{i}{d}\cdot[\gcd(i,n)=d]
虽然看起来比较废话但很关键
然后再变形，中括号里除以d变成\gcd(\dfrac{i}{d},\dfrac{n}{d})=1，其实就是如果\dfrac{i}{d}和\dfrac{n}{d}互质，那么他们都乘d以后的\gcd就是d
n\sum_{d | n}\sum_{i=1}^n\frac{i}{d}\cdot[\gcd(\frac{i}{d},\frac{n}{d})=1]
然后让i替代\dfrac{i}{d}
n\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}i\cdot[\gcd(i,\frac{n}{d})=1]
又因为这个\dfrac{n}{d},d是n的“一对”因数，所以这个式子可以直接写成一个更好看的形式：
n\sum_{d|n}\sum_{i=1}^{d}i\cdot[\gcd(i,d)=1]
然后这就有点欧拉\varphi函数的意思了
关键是那个i很碍眼，所以当然是要再看一波题解
由于\gcd(i,d)=\gcd(d-i,d)
这个和欧几里得法求\gcd很像，具体证明可以去这里看
所以考虑\sum_{i=1}^{d}i\cdot[\gcd(i,d)=1]里的每一个i和d-i，如果\gcd(i,d)\neq 1肯定就不用管，如果等于1，那么这两项的值就是d
那么有多少对\gcd(i,d)=\gcd(d-i,d)=1？肯定是\dfrac{\varphi(d)}{2}，注意这里说的是多少对
但是很容易发现，d=1是上面式子成0了，不成立，所以应该给\sum中的分子加上1然后下取整，就避免了这个情况
然后更准确的答案就表述为：
n\sum_{d|n}\lfloor\frac{\varphi(d)\cdot d+1}{2}\rfloor
其实这时已经可以O(\sqrt n)回答了，但还可以做的更好
然后对于每一个枚举到的$i$，实际上就是上式中的每一个$d$，然后按公式给$f_j$加上就好
-------------
## 小总结
~~当然我做的题太少可能说的不全~~
其实这种$\gcd,\operatorname{lcm}$有关的问题，很多都是转变成$[\gcd=\cdots]\times \cdots$的形式，$\cdots$都是数，然后和$\varphi$结合起来
有时这个转换的方式就是通过加上一个$\sum_{d|n}$，其它的还没遇见，遇见了可能会写在这里
反正$\gcd$这种最容易联想到的就是$\varphi$了
```cpp
#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\n",f[n]*n);
}
return 0;
}
```