正题

题目链接:https://www.luogu.com.cn/problem/P2257

---

题目大意

给出$n,m$，求$$\sum _{i=1}^n\sum _{j=1}^m[gcd(i,j)\in p]$$

定义$p$是质数集

---

解题思路

首先考虑定义$$f(x)=\sum _{i=1}^n\sum _{j=1}^m[gcd(i,j)==x]$$
然后有$F(x)={\sum }_{d|x}f(x)=\lfloor \frac{n}{x}\rfloor \lfloor \frac{m}{x}\rfloor$
根据莫比乌斯反演就有$$f(d)=\sum _{i|d}\mu (\frac{i}{d})F(d)$$即$$f(d)=\sum _{i|d}\mu (\frac{i}{d})\lfloor \frac{n}{x}\rfloor \lfloor \frac{m}{x}\rfloor$$枚举质数$p$
然后有$$ans=\sum _p^n\sum _{d=1}^n\mu (d)\lfloor \frac{n}{pd}\rfloor \lfloor \frac{m}{pd}\rfloor$$
$$\Rightarrow ans=\sum _i^n\lfloor \frac{n}{i}\rfloor \lfloor \frac{m}{i}\rfloor \sum _{d|i}\mu (\frac{i}{d})$$

预处理${\sum }_{d|i}\mu (\frac{i}{d})$的前缀和即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e7+10; int T,n,m,cnt; int pri[N],mu[N],g[N]; long long ans; bool vis[N]; void prime(){mu[1]=1;for(int i=2;i<N;i++){if(!vis[i])mu[i]=-1,pri[++cnt]=i;for(int j=1;j<=cnt&&pri[j]*i<N;j++){vis[i*pri[j]]=1;if(i%pri[j]==0)break;mu[i*pri[j]]=-mu[i];}}for(int j=1;j<=cnt;j++)for(int i=1;pri[j]*i<N;i++)g[i*pri[j]]+=mu[i];for(int i=1;i<N;i++)g[i]+=g[i-1];return; } int main() {prime();scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);if(n>m)swap(n,m);ans=0;for(int l=1,r;l<=n;l=r+1){r=min(n/(n/l),m/(m/l));ans+=1ll*(n/l)*(m/l)*(g[r]-g[l-1]);}printf("%lld\n",ans);} }

总结

以上是生活随笔为你收集整理的P2257-YY的GCD【莫比乌斯反演】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。