本文共 3931 字，大约阅读时间需要 13 分钟。

莫比乌斯函数线性筛：

const int maxm=1e6+5;int notprime[maxm];int prime[maxm],cnt;int mob[maxm];void Minit(){
       mob[1]=1;    for(int i=2;i
   
    =maxm)break;            notprime[prime[j]*i]=1;            mob[prime[j]*i]=i%prime[j]?-mob[i]:0;            if(i%prime[j]==0)break;        }    }}
   

莫比乌斯函数性质：

μ是莫比乌斯函数

1.∑μ(d) = [n==1] (d|n，即d是n的因子) 2. ∑(μ(d)/d) = (ϕ(n)/n) (d|n，ϕ是欧拉函数)，这个性质把莫比乌斯函数和欧拉函数联系起来了

莫比乌斯反演：

其他：

---

P2257 YY的GCD

题意：

给N,M，求有多少对1<=x<=N，1<=y<=M，满足gcd(x,y)=素数

思路:

code:

#include
   
    using namespace std;const int maxm=1e7+5;int notprime[maxm];int prime[maxm],cnt;int mu[maxm];int f[maxm];long long sum[maxm];void init(){
       //预处理莫比乌斯函数    mu[1]=1;    for(int i=2;i
    
     =maxm)break;            notprime[prime[j]*i]=1;            mu[prime[j]*i]=i%prime[j]?-mu[i]:0;            if(i%prime[j]==0)break;        }    }    //预处理sum[k]=∑mu(k/n)    for(int j=0;j
     
      >T;    while(T--){
           int n,m;        cin>>n>>m;        if(n>m)swap(n,m);        long long ans=0;        for(int l=1,r;l<=n;l=r+1){
               r=min(n/(n/l),m/(m/l));            ans+=(long long)(n/l)*(m/l)*(f[r]-f[l-1]);        }        cout<
      
       <
      
     
    
   

---

P3455 [POI2007]ZAP-Queries

题意：

给a,b,d，问有多少组x,y，满足1<=x<=a,1<=y<=b,gcd(x,y)=d

思路：

图中第三行f(n)计算完之后 因为gcd(i,j)=k，gcd(i/k,j/k)=1， 那么问题就变为计算f(1)，范围变为1<=x<=a/d，1<=y<=b/d，也就是图中的f(d)

code：

#include
   
    using namespace std;const int maxm=5e4+5;int notprime[maxm];int prime[maxm],cnt;int mu[maxm];int sum[maxm];void init(){
       mu[1]=1;    for(int i=2;i
    
     =maxm)break;            notprime[prime[j]*i]=1;            mu[prime[j]*i]=i%prime[j]?-mu[i]:0;            if(i%prime[j]==0)break;        }    }    for(int i=1;i
     
      >T;    while(T--){
           int a,b,d;        scanf("%d%d%d",&a,&b,&d);        long long ans=0;        int up=min(a/d,b/d);        for(int l=1,r;l<=up;l=r+1){
               r=min((a/d)/(a/d/l),(b/d)/(b/d/l));            ans+=(long long)(a/d/l)*(b/d/l)*(sum[r]-sum[l-1]);        }        printf("%lld\n",ans);    }    return 0;}
     
    
   

---

hdu1695 GCD

题意：

给a,b,c,d,k，问有多少组x,y，满足a<=x<=b,c<=y<=d,gcd(x,y)=k，数对(x,y)为无序对

爆炸a和c等于1，0<b,d<=1e5，0<=k<=1e5

思路：

和上一题一样，但是这题是无序对，需要去重

code：

#include
   
    using namespace std;#define int long longconst int maxm=1e6+5;int notprime[maxm];int prime[maxm],cnt;int mob[maxm];void Minit(){
       mob[1]=1;    for(int i=2;i
    
     =maxm)break;            notprime[prime[j]*i]=1;            mob[prime[j]*i]=i%prime[j]?-mob[i]:0;            if(i%prime[j]==0)break;        }    }    for(int i=1;i
     
      m)swap(n,m);//令n<=m    int ans=0;    for(int l=1,r;l<=n;l=r+1){
           r=min(n/(n/l),m/(m/l));        ans+=(n/l)*(m/l)*(mob[r]-mob[l-1]);    }    //这题需要减掉重复的,因为题目的是无序对    int rep=0;    for(int l=1,r;l<=n;l=r+1){
   //n<=m,只有小于等于的部分才可能重复,因此这里只考虑n不考虑m        r=n/(n/l);        rep+=(n/l)*(n/l)*(mob[r]-mob[l-1]);    }    return ans-rep/2;}signed main(){
       Minit();    int T;cin>>T;    signed cas=1;    while(T--){
           int a,b,c,d,k;cin>>a>>b>>c>>d>>k;        int ans=solve(b,d,k);        printf("Case %d: ",cas++);        cout<
      
       <
      
     
    
   

---

P2522 [HAOI2011]Problem b

题意：

给a,b,c,d,k，问有多少组x,y，满足a<=x<=b,c<=y<=d,gcd(x,y)=k

思路:

做过上一题 P3455 [POI2007]ZAP-Queries 的话就会发现那题就是a=1,c=1的情况

设f(A,B)是满足1<=x<=A,1<=y<=B,gcd(x,y)=k的数对数量 由容斥原理可得ans=f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1) 式子的推导过程在上一题有了这里就不推了

code:

#include
   
    using namespace std;const int maxm=5e4+5;int notprime[maxm];int prime[maxm],cnt;int mu[maxm];int sum[maxm];void init(){
       mu[1]=1;    for(int i=2;i
    
     =maxm)break;            notprime[prime[j]*i]=1;            mu[prime[j]*i]=i%prime[j]?-mu[i]:0;            if(i%prime[j]==0)break;        }    }    for(int i=1;i
     
      >T;    while(T--){
           int a,b,c,d,k;        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);        long long ans=ask(b,d,k)-ask(a-1,d,k)-ask(b,c-1,k)+ask(a-1,c-1,k);        printf("%lld\n",ans);    }    return 0;}
     
    
   

---

转载地址：http://qtzv.baihongyu.com/