題意

多組詢問，每次給定 \(n\) ,求：\(\sum_{i=1}^nlcm(i,n)\) 。

• \(\rm T \leq 3\times 10^4\ ,n \leq 10^6\)。

分析

• 推式子:
  \[\sum_{i=1}^n{\frac{in}{gcd(i,n)}}\]
• 枚舉 \(gcd\) :
  \[n\sum_{d|n}{\sum_{i=1}^n[gcd(i,n)=d]\frac{i}ze8trgl8bvbq}\]

\[n\sum_{d|n}{\sum_{i=1}^{\frac{n}ze8trgl8bvbq}[i\perp \frac{n}ze8trgl8bvbq]i}\]

\[n\sum_{d|n}{\sum_{i=1}^d{[i\perp d]i}}\]

• 對于后面的求和可以看成函數(shù) \(f_d\) ,表示所有和 \(d\) 互質(zhì)的數(shù)字之和。

• 根據(jù)輾轉(zhuǎn)相減可以得到 \(gcd(i,d)=gcd(d-i,d)\) ,表明所有與 \(d\) 互質(zhì)的數(shù)字可以兩兩配對得到 \(d\) 。

• 所以 \(f_d=\frac{\varphi(d)*d}{2}\) 。

• 處理 \(\varphi\) 的時間 \(O(n)\) 加上單次處理的時間 \(O(\sqrt n)\),總時間復(fù)雜度為 \(O(2n)\) 。

技巧：輾轉(zhuǎn)相減的使用

代碼

#include<bits/stdc++.h> using namespace std; #define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].last,v=e[i].to) #define rep(i,a,b) for(int i=a;i<=b;++i) #define pb push_back typedef long long LL; inline int gi(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return x*f; } template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;} template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;} const int N=1e6 + 7; int T,pric,n; int phi[N],pri[N],vis[N]; LL f[N]; void pre(int Num){phi[1]=1;int to;for(int i=2;i<=Num;++i){if(!vis[i]) { phi[i]=i-1,pri[++pric]=i;}for(int j=1;j<=pric&&(to=i*pri[j])<=Num;++j){vis[to]=1;if(i%pri[j]==0){phi[to]=phi[i]*pri[j];break;}phi[to]=phi[i]*phi[pri[j]];}} } int main(){T=gi();pre(1000000);f[1]=1;for(int i=2;i<=1000000;++i) f[i]=1ll*phi[i]*i/2;while(T--){n=gi();LL ans=0;int l=1,r=1000;while(l<r){int mid=l+r+1>>1;if(mid*mid<=n) l=mid;else r=mid-1;}for(int i=1;i<=l;++i)if(n%i==0){ans+=f[i];if(i*i!=n)ans+=f[n/i];}printf("%lld\n",ans*n);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/yqgAKIOI/p/9801778.html

總結(jié)

以上是生活随笔為你收集整理的[Luogu1891]疯狂LCM[辗转相减法]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。