正題

P3455

---

題目大意

有T組詢問，每組詢問給出n,m,c，求$$\sum _{i=1}^n\sum _{j=1}^m[(i,j)=c]$$

---

解題思路

可以先對n,m除c這樣就使得求出的數都有c的因子，得到式子如下
$$\begin{gathered} \sum _{i=1}^n\sum _{j=1}^m[(i,j)=1] \\ \sum _{i=1}^n\sum _{j=1}^m\sum _{d|i,d|j}\mu (d) \\ \sum _{d=1}^{min(n,m)}\mu (d)\times ?\frac{n}{d}?\times ?\frac{m}{d}? \end{gathered}$$
然后整除分塊求解

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

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 50050 using namespace std; int T,n,m,d,w,ans,mu[N],p[N],prime[N]; void work() {p[1]=1;mu[1]=1;for(int i=2;i<=50000;++i){if(!p[i]){prime[++w]=i;mu[i]=-1;}for(int j=1;j<=w&&i*prime[j]<=50000;++j){p[i*prime[j]]=1;if(i%prime[j]==0){mu[i*prime[j]]=0;break;}else mu[i*prime[j]]=-mu[i];}}for(int i=2;i<=50000;++i)mu[i]+=mu[i-1];return; } int main() {work();scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&d);n/=d;m/=d;ans=0;for(int l=1,r=0;l<=min(n,m);l=r+1){r=min(n/(n/l),m/(m/l));ans+=(mu[r]-mu[l-1])*(n/l)*(m/l);}printf("%d\n",ans);}return 0; }

總結

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

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