一、題目描述：

　　$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++!$