正題

P2257

---

題目大意

給你T組詢問，每組詢問給出n,m，讓你求 $1\le x\le n,1\le y\le m$ 且 $gcd(x,y)=prime$ 的方案數

---

解題思路

根據題意，有

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

考慮把prime拿出來枚舉

$$\begin{gathered} \sum _{p\in prime}^n\sum _{i=1}^{n/p}\sum _{j=1}^{m/p}[gcd(i,j)=1] \\ \sum _{p\in prime}^n\sum _{i=1}^{n/p}\sum _{j=1}^{m/p}\sum _{d|i,d|j}\mu (d) \\ \sum _{p\in prime}^{min(n,m)}\sum _{d=1}^{min(n,m)/p}\mu (d)\times ?\frac{n}{dp}?\times ?\frac{m}{dp}? \end{gathered}$$

然后可以考慮改變枚舉變量

可以發現后面的兩個整除都與dp有關，那么考慮枚舉dp，那么有

$$\begin{gathered} \sum _{k=1}^{min(n,m)}\sum _{p\in prime,p|k}\mu (\frac{k}{p})\times ?\frac{n}{k}?\times ?\frac{m}{k}? \\ \sum _{k=1}^{min(n,m)}?\frac{n}{k}??\frac{m}{k}?\sum _{p\in prime,p|k}\mu (\frac{k}{p}) \end{gathered}$$

對于后面的${\sum }_{p\in prime,p|k}\mu (\frac{k}{p})$，可以預處理，先枚舉質數，然后枚舉倍數，然后計算貢獻

對于前面的一段再整除分塊就好了

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

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 10000010 using namespace std; ll T,n,m,ans,w,p[N],g[N],mu[N],prime[N]; const ll MX=1e7; void work() {p[1]=mu[1]=1;for(ll i=2;i<=MX;++i){if(!p[i]){mu[i]=-1;prime[++w]=i;}for(ll j=1;j<=w&&i*prime[j]<=MX;++j){p[i*prime[j]]=1;if(i%prime[j]==0)break;else mu[i*prime[j]]=-mu[i];}}for(ll i=1;i<=w;++i)for(ll j=1;j*prime[i]<=MX;++j)g[j*prime[i]]+=mu[j];//對每個數提出一個質因數計算mu的貢獻for(ll i=2;i<=MX;++i)g[i]+=g[i-1];return; } int main() {scanf("%lld",&T);work();while(T--){scanf("%lld%lld",&n,&m);ans=0;for(ll l=1,r=0;l<=min(n,m);l=r+1){r=min(n/(n/l),m/(m/l));ans+=(n/l)*(m/l)*(g[r]-g[l-1]);}printf("%lld\n",ans);}return 0; }

總結

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

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