P1891 疯狂 LCM 题解

一、题目描述：

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