以下設\(n\ge m\)。

首先,一個點\((x,y)\)到\((0,0)\)的路徑上經過的點的數量(不包括首尾)為\(gcd(x,y)-1\)。

所以它的能量損耗為\(2\times gcd(x,y)-1\)。

考慮如何統計\(\sum_{i=1}^n\sum_{j=1}^m 2\times gcd(i,j)-1\)。

記\(f_x=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=x]\),即\(1\le i\le n,1\le j\le m\)時,\(gcd(i,j)=x\)的數量。

我們再記\(F_x=\sum_{x|i}f_i\)。

莫名其妙想到了莫比烏斯反演,但是在這里顯然不能用

我們發現\(F(x)\)其實就是滿足\(1\le i\le n,1\le j\le m,i|x,j|x\)的\((i,j)\)數量,即\(\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{x}\rfloor\)。

我們還發現\(f_i=F_i-\sum_{x=2}^{\lfloor\frac{n}{i}\rfloor}f_{xi}\),即\(F_i\)減去 \(f_k\)的和 ,其中\(k\)是\(i\)的倍數且不等于\(i\)。

于是我們從大到小枚舉\(i\)并計算\(f_i\),答案就是\(\sum_{i=1}^n(2\times i-1)\times f_i\)。

根據調和級數,其時間復雜度為\(O(nlogn)\)。

code:

#include<bits/stdc++.h> using namespace std; int n,m; long long num[100010],ans; int main(){scanf("%d%d",&n,&m),n<m?swap(n,m),0:0;for(int i=n;i>=1;--i){num[i]=1ll*(n/i)*(m/i);for(int j=i+i;j<=n;j+=i)num[i]-=num[j];ans+=(2*i-1)*num[i];}printf("%lld",ans);return 0; }

轉載于:https://www.cnblogs.com/xryjr233/p/BZOJ2005.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的[2019.1.14]BZOJ2005 [Noi2010]能量采集的全部內容，希望文章能夠幫你解決所遇到的問題。

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