简要题意
\(T\) 组数据，每组数据给出一个 \(n\)，计算：
\[\sum_{i=1}^{n}{\operatorname{lcm}(i,n)} \]\(1 \leq T \leq 3\times 10^5,1 \leq n \leq 10^{6}\)
思路
比较快乐的推式子题。
\[\begin{aligned} &\sum_{i=1}^{n}{\operatorname{lcm}(i,n)}\\ &=\sum_{i=1}^{n}{\frac{in}{\gcd(i,n)}}\\ &=\frac{1}{2}(\sum_{i=1}^{n-1}{\frac{n^2}{\gcd(i,n)}})+n&\texttt{(1)}\\ &=\frac{1}{2}({\sum_{d\mid n}{\frac{n^2\varphi(n\div d)}{d}}})+n&\texttt{(2)}\\ &=n(\sum_{d\mid n}{\frac{1}{2}d\varphi(d)})+n&\texttt{(3)} \end{aligned} \]- \(\texttt{(1)}\)：把上式拆成两个等价的式子的和除以二，发现错位相加就可以凑出来了。
- \(\texttt{(2)}\)：我们改为枚举 \(\gcd(i,n)\) 的值，不难发现 \(\gcd(i,n)\mid n\)。
- \(\texttt{(3)}\)：改为枚举上式中的 \(n\div d\)，不知道为什么，直接算上式会有除以二的误差。
然后就可以做了。
时间复杂度 \(O(n\log n)\)。
代码
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
int phi[10000005],t,n;
int ans[10000005];
void phi_table(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!phi[i]) {
for (int j = i; j <= n; j += i) {
if (!phi[j]) {
phi[j] = j;
}
phi[j] = phi[j] / i * (i - 1);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;(i*j)<=n;j++){
ans[i*j]+=j*phi[j]/2;
}
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>t;
phi_table(1e6);
while(t--){
cin>>n;
cout<<((n*ans[n])+n)<<'\n';
}
return 0;
}