正題

P2398

---

題目大意

給出n，求$$\sum _{i=1}^n\sum _{j=1}^{n}gcd(i,j)$$

---

解題思路

考慮先枚舉gcd，那么有

$$\sum _{d=1}^{n}d\sum _{i=1}^{n/d}\sum _{j=1}^{n/d}[gcd(i,j)=1]$$

$$\begin{gathered} \phi (n)=\sum _{i=1}^n[gcd(i,n]=1] \\ \sum _{k=1}^n\phi (k)=\sum _{i=1}^n\sum _{j=1}^i[gcd(i,j)=1] \end{gathered}$$

原式后面一段比上面多了 $j>i$ 的情況，這種情況的方案數和 $j\le i$ 的方案數是相等的，可以直接乘2，不過要把 $\phi (1)$ 重復計算的減去

那么原式為

$$\sum _{d=1}^{n}d(2\times \sum _{i=1}^{n/d}\phi (i)+1)$$

后面一段可以用前綴和做，然后可以直接整除分塊

時間復雜度 $O(\sqrt{n})$

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 100100 using namespace std; ll n,w,ans,p[N],phi[N],prime[N]; const ll MX=100000; void work() {phi[1]=1;for(ll i=2;i<=MX;++i){if(!p[i]){prime[++w]=i;phi[i]=i-1;}for(ll j=1;j<=w&&i*prime[j]<=MX;++j){p[i*prime[j]]=1;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else phi[i*prime[j]]=phi[i]*(prime[j]-1);}}for(ll i=2;i<=n;++i)phi[i]+=phi[i-1];return; } int main() {scanf("%lld",&n);work();for(ll l=1,r=0;l<=n;l=r+1){r=n/(n/l);ans+=(phi[n/l]*2-1)*(r+l)*(r-l+1)/2;}printf("%lld",ans);return 0; }

總結

以上是生活随笔為你收集整理的【数论】GCD SUM（P2398）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。