題意: 給定a，b，d求gcd(x,y)=d的對數(1<=x<=a,1<=y<=b)

思路：按照套路來先設f(n)為gcd(x,y)=n的對數,g(n)表示為 n | gcd(x,y)的對數,則g(n)=∑_n|df(d)=a/n*b/n

f(n)=∑_n|dg(d)*mu(d/n),令t=d/n則f(n)=∑_t=1g(t*n)*mu(t)，然后求f(d)就行了

#include<iostream> #include<algorithm> #include<string.h> #include<string> #include<vector> #include<cstdio> #include<queue> #include<map> #include<set> #include<math.h> using namespace std; const int inf=0x3f3f3f3f; const int maxn=1e5+5; typedef long long ll; int dir[4][2]={-1,0,1,0,0,-1,0,1}; int prime[maxn/10]; int tot; int mu[maxn]; int sum[maxn]; int vis[maxn]; void table(){memset(vis,0,sizeof(vis));memset(sum,0,sizeof(sum));memset(mu,0,sizeof(mu));tot=0;mu[1]=1;vis[0]=vis[1]=1;sum[1]=1;for(int i=2;i<maxn;i++){if(!vis[i]){prime[tot++]=i;mu[i]=-1;}sum[i]=sum[i-1]+mu[i];for(int j=0;j<tot&&i*prime[j]<maxn;j++){vis[i*prime[j]]=1;if(i%prime[j]){mu[i*prime[j]]=-mu[i];}else break;}} } int main(){ll t;ios::sync_with_stdio(false);table();cin>>t;while(t--){ll a,b,d;cin>>a>>b>>d;a/=d;b/=d;ll limit=min(a,b);ll ans=0;for(ll x=1,y;x<=limit;){//cout<<x<<endl;y=min(a/(a/x),b/(b/x));ans+=(a/x)*(b/x)*(sum[y]-sum[x-1]);x=y+1;}cout<<ans<<endl;} }

?

轉載于:https://www.cnblogs.com/azznaz/p/10727402.html

總結

以上是生活随笔為你收集整理的洛谷 P3455 [POI2007]ZAP-Queries (莫比乌斯反演)的全部內容，希望文章能夠幫你解決所遇到的問題。

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