莫比乌斯反演+例题

问题引入：

添加链接描述
给定N和M和D，求满足1<=x<=N,1<=y<=M且gcd(x,y)=D的点对(x,y)的个数
1<=N,M<=1000000

莫比乌斯函数

μ
μ(n) = 1 , n=1
μ(n) = (-1)^k^, n=p1 * p2 * ... * Pk
（x有奇数个质因子时为-1，x有偶数个质因子时为1）
μ(n) = 0 其他情况（x存在平方因子）

莫比乌斯线性筛：

int prime[MAXN],prime_tot;
bool prime_tag[MAXN];
int mu[MAXN];
void pre_calc(int lim)
{
    mu[1]=1;
    for(int i=2;i<=lim;i++)
    {
        if(!prime_tag[i])
        {
            prime[++prime_tot]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=prime_tot;j++)
        {
            if(i*prime[j]>lim)break;
            prime_tag[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]==0;
                break;
            }
            else 
            {
                mu[i*prime[j]]=-mu[i];
            }
        }
    }
 } 

狄利克雷卷积介绍

狄利克雷卷积：( f * g )(n) = ∑d|nf(d)g(n/d)
d是n的因子
积性函数是指一个定义域为正整体n的算术函数f(n)
积性函数：对于任意互质的整数a和b有性质f(ab)=f(a)f(b)的函数
完全积性函数：对于任意整数a和b有性质f(ab)=f(a)f(b)的函数
若n = p1^a1^ p2^a2^ * ..... * pk^ak^
则 f(n) = f(p1^a1^) *f(p2^a2^) * ..... * f(pk^ak^)
常见的积性函数：
*欧拉函数： φ(n)**
n=∑i/nφ(i)
莫比乌斯函数：μ(n)
单位函数：Id(n)=n
不变函数：1(n)=1
幂函数：Idk(n)=n^k^
因子个数函数：d(n),d= 1 * 1
因子和函数：σ(n),σ=1 * Id
因子函数：σk(n)
狄利克雷卷积单位元：ε = [n==1]
（当n=1时，ε=1，否则等于0）
μ * 1 = ε

莫比乌斯反演

解决问题：

[a'/d]（向下取整）在一段区间内并不变化，所以最多取到2√a'
按照取值将O（√n）段，对μ（d）计算前缀和，然后计算即可

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=1e5+5;
int p[N+10],check[N+10],tot;
int mu[N],sum[N];
int T,n,m,d,ans;

void init(){
    memset(check,1,sizeof check);
    mu[1]=1;
    for(int i=2;i<=N;i++){
        if (check[i]){
            p[++tot]=i;
            mu[i]=-1;
        }
        for (int j=1;j<=tot && p[j]*i<=N;j++){
            check[i*p[j]]=0;
            if (i%p[j]==0){
                mu[i*p[j]]=0;
                break;    
            }
            else mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=1;i<=N;i++)sum[i]=mu[i]+sum[i-1];    //维护前缀和
}

int calc(int n,int m){    //求[1,n][1,m]区间内互质的(x,y)的对数
    int ret=0;
    if (n>m) swap(n,m);
    for (int L=1,R=0;L<=n;L=R+1){
        R=min(n/(n/L),m/(m/L));        // 分段
        ret+=(sum[R]-sum[L-1])*(n/L)*(m/L);
    }
    return ret;
}

int main(){
    init();
    scanf("%d",&T);
    while (T--){
        scanf("%d%d%d",&n,&m,&d);
        ans=calc(n/d,m/d);
        printf("%d\n",ans);
    }
    return 0;
}