当前位置: 代码迷 >> 综合 >> HDU 1695 GCD 莫比乌斯反演
  详细解决方案

HDU 1695 GCD 莫比乌斯反演

热度:20   发布时间:2023-12-22 14:14:19.0

题意:

求【1,b】和【1,d】两个区间内gcd为k的数对的数量,其中(x,y)和(y,x)看作同一数对。

题解:

莫比乌斯反演入门题。

基本套路,设f(k)和g(k),g(k)很容易求,再通过莫比乌斯反演求f(k)。

我的另一篇博客中莫比乌斯反演的过程与这道题类似,且已经写得很详细了。

最后可得式子(方便起见,不妨令b<=d,不满足则交换两者值,显然不影响结果)

线性筛预处理出莫比乌斯函数的值,此时已经可以的求解问题了。

当然本题由于(x,y)和(y,x)为同一数对,因此需要考虑去重。

重复的原因在于,【1,b】和【1,b】的数对除了(k,k)外都有两个,假设此中数对有ans1对

则重复的为对,因此答案为

(PS:当ans1不为0时,必定为奇数,因此整数除法中等价于,所以代码中直接使用了后者

代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define m_p make_pair
#define p_b push_back
#define For(i,a,b) for(int i=a;i<=b;i++)
#define ls (rt<<1)
#define rs ((rt<<1)|1)
#define mst(a,b) memset(a,b,sizeof(a))
const int MAXN=1e5+5;
const db eps=1e-8;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int seed=131;
bool notprime[MAXN];
int prime[MAXN],cnt,mu[MAXN];
void init(){mu[1]=notprime[1]=1;for(int i=2;i<MAXN;i++){if(!notprime[i]) prime[cnt++]=i,mu[i]=-1;for(int j=0;j<cnt&&prime[j]*i<MAXN;j++){notprime[prime[j]*i]=1;if(i%prime[j]==0) break;mu[i*prime[j]]=-mu[i];} }
}
int main(){
//	freopen("in.txt","r",stdin);int t,a,b,c,d,k;init();cin>>t;For(cas,1,t){cin>>a>>b>>c>>d>>k;ll ans=0;if(k!=0){ll ans1=0;if(b>d) swap(b,d);d/=k,b/=k;for(int i=1;i<=b;i++){ans+=mu[i]*(d/i)*1ll*(b/i);}for(int i=1;i<=b;i++){ans1+=mu[i]*(b/i)*1ll*(b/i);}ans-=ans1/2;}cout<<"Case "<<cas<<": ";cout<<ans<<"\n";}return 0;
}

 

优化:

同样很套路的,考虑到在很多时候的值是不变的,因此可以考虑通过数论分块对之进行优化。

若b与d相同时,很显然数论分块的复杂度为,而两者不相等时,考虑到每一块的结尾一定是b或d的因子,那么再怎么差也不过是块,因此也是根号级别的。

代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define m_p make_pair
#define p_b push_back
#define For(i,a,b) for(int i=a;i<=b;i++)
#define ls (rt<<1)
#define rs ((rt<<1)|1)
#define mst(a,b) memset(a,b,sizeof(a))
const int MAXN=1e5+5;
const db eps=1e-8;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int seed=131;
bool notprime[MAXN];
int prime[MAXN],cnt,mu[MAXN];
void init(){mu[1]=notprime[1]=1;for(int i=2;i<MAXN;i++){if(!notprime[i]) prime[cnt++]=i,mu[i]=-1;for(int j=0;j<cnt&&prime[j]*i<MAXN;j++){notprime[prime[j]*i]=1;if(i%prime[j]==0) break;mu[i*prime[j]]=-mu[i];} }for(int i=1;i<MAXN;i++) mu[i]+=mu[i-1];
}
int main(){
//	freopen("in.txt","r",stdin);int t,a,b,c,d,k;init();cin>>t;For(cas,1,t){cin>>a>>b>>c>>d>>k;ll ans=0;if(k!=0){ll ans1=0,tt=0,tt1=0;if(b>d) swap(b,d);d/=k,b/=k;for(int l=1,r;l<=b;l=r+1){tt=b/l,tt1=d/l;r=min(b/tt,d/tt1);ans+=(mu[r]-mu[l-1])*tt*tt1;}for(int l=1,r;l<=b;l=r+1){tt=b/l;r=b/tt;ans1+=(mu[r]-mu[l-1])*tt*tt;}ans-=ans1/2;}cout<<"Case "<<cas<<": ";cout<<ans<<"\n";}return 0;
}