一、题目描述：
$T$ 组数据，每组数据给定 $n$，求$\sum_{i=1}^{n}lcm(i,n)$
数据范围：$1\le T \le 3\times 10^5，1\le n\le 1\times 10^6$ 。
二、解题思路：
个人觉得思维难度不大，只是要记住一个结论：
$\sum_{d\mid n}d=\frac{\varphi(n)\times n}{2}$
这个公式对于 $1$ 以外的正整数都成立。
证明一：$若\ gcd(i,n)=1,则\ gcd(n-i,n)=1$
$反证：假设gcd(n-i,n)=k,k\ 为大于\ 1\ 的正整数$
$则n-i=a_1\times k , n=a_2 \times k , i=(a_2-a_1)\times k$
$所以\ gcd(i,n)\ 至少为\ k，矛盾，命题得证$
证明二：$\sum_{d\mid n}d=\frac{\varphi(n)\times n}{2}$
$由证明一得,若\ gcd(i,n)=1,则\ gcd(n-i,n)=1$
$当\ i\ne n-i\ 时，(i,n-i)\ 对\ \varphi(n)\ 的贡献为\ 2,对\ \sum_{d\mid n}d\ 的贡献为\ n=2\times \frac{n}{2},成立。$
$当\ i=n-i\ 时，(i,n-i)\ 对\ \varphi(n)\ 的贡献为\ 1,对\ \sum_{d\mid n}d\ 的贡献为\ \frac{n}{2}=1\times \frac{n}{2},成立。$
$综上，\sum_{d\mid n}d=\frac{\varphi(n)\times n}{2}，命题得证。$
那这个题就不难了，推一下式子就行了，顺便证一下线性筛 $\varphi()$ 函数。
$已知若x=p_1^{e_1}\times p_2^{e_2}\times ...\times p_n^{e_n}$
$则\varphi(x)=n\times \prod_{i=1}^{n}(1-\frac{1}{p_i})$
$欧拉筛中，每个合数会被自己最小的质因子筛掉$
$设当前的数为\ x,最小质因子为\ y,另一个因数为\frac{x}{y}$
$首先，x 必然有所有 \frac{x}{y} 的质因子$
$当y\mid \frac{x}{y} ,\varphi(x)=\varphi(\frac{x}{y})\times y$
$当y\nmid \frac{x}{y},\varphi(x)=\varphi(\frac{x}{y})\times(y-1)$
现在这个题就做完了，时间复杂度 $O(n+T\sqrt{n})$。
三、完整代码：
1 #include<iostream> 2 #define N 1000010 3 #define lim 1000000 4 using namespace std; 5 int T,n,cnt; 6 long long ans,f[N]; 7 int p[N],vis[N],phi[N]; 8 void pre_work() 9 { 10 phi[1]=f[1]=1; 11 for(int i=2;i<=lim;i++) 12 { 13 if(!vis[i]) p[++cnt]=i,phi[i]=i-1; 14 for(int j=1;j<=cnt&&p[j]*i<=lim;j++) 15 { 16 vis[i*p[j]]=1; 17 if(i%p[j]==0){ 18 phi[i*p[j]]=phi[i]*p[j]; 19 break; 20 }else phi[i*p[j]]=phi[i]*phi[p[j]]; 21 } 22 } 23 for(int i=2;i<=lim;i++) 24 f[i]=1ll*i*phi[i]/2; 25 } 26 void solve() 27 { 28 cin>>n;ans=0; 29 for(int i=1;i*i<=n;i++) 30 if(n%i==0) 31 { 32 ans+=f[i]; 33 if(i*i!=n) ans+=f[n/i]; 34 } 35 cout<<ans*n<<'\n'; 36 } 37 int main() 38 { 39 ios::sync_with_stdio(false); 40 cin.tie(0);cout.tie(0); 41 cin>>T;pre_work(); 42 for(int i=1;i<=T;i++) 43 solve(); 44 return 0; 45 }
四、写题心得：
写数学题就是推公式比较耗时间，但是有一种其他题都享受不到的快感！收获经验如下：
$1、线性筛\ varphi()\ 函数的方法。=> Exp++!$
$2、关于\ \varphi()\ 函数的一个公式。=> Exp++!$