正題

題目鏈接：https://www.luogu.org/problemnew/show/P1447

---

題目大意

求$$\sum _{i=1}^n\sum _{j=1}^{m}gcd(i,j)?2?1$$

---

解題思路

設$f_i$表示$gcd(x,y)==i(x\in [1..n],y\in [1..m])$的個數(shù)。
然后首先如果不是考慮$i$為最大的公約數(shù)的話那么個數(shù)就是$(n/i)?(m/i)$

然后考慮容斥減去，假設一個數(shù)的最大公約數(shù)是$y$而且擁有$x$這個公約數(shù)的話那么一定滿足
$$y=kx(k\in \mathbb{N})$$
那么就減去$f_{k?i}$就好了

所以推得狀態(tài)轉(zhuǎn)移方程$$f_i=(n/i)?(m/i)?\sum _{k=1}^{k?i\le min\{n,m\}}{f}_{i?k}$$

時間復雜度$O(n\log \log n)$

---

$code$

#include<cstdio> #include<algorithm> #define ll long long using namespace std; ll n,m,ans,f[101000]; int main() {scanf("%lld%lld",&n,&m);if(n>m) swap(n,m);for(ll i=n;i>=1;i--){f[i]=(n/i)*(m/i);for(ll j=2*i;j<=n;j+=i)f[i]-=f[j];ans+=(i*2-1)*f[i];}printf("%lld",ans); }

總結(jié)

以上是生活随笔為你收集整理的P1447-[NOI2010]能量采集【GCD,数论,容斥】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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