【Luogu】P3455Zip-Queries（莫比乌斯反演）

　　题目链接

　　真是神TM莫比乌斯

　　首先来看一个神奇的结论：求gcd（x，y）==k的对数，其中1<=x<=n,1<=y<=m

　　等同于求gcd(x,y)==1的对数，其中1<=x<=n/k,1<=y<=m/k

　　然后这题就变成了求gcd(x,y)==1的对数，其中1<=x<=n/k,1<=y<=m/k

　　我们再把莫比乌斯反演的定义copy一下

　　设有函数$F(n),f(n)$定义在非负整数集合上

　　有$F(n)=sumlimits_{d|n}^{}f(d)$

　　那么则有$f(n)=sumlimits_{d|n}^{}miu(d)F(frac{n}{d})$

　　或者说如果有$F(n)=sumlimits_{n|d}^{}f(d)$

　　那么$f(n)=sumlimits_{n|d}^{}miu(frac{d}{n})F(d)$

　　miu函数定义如下:

　　若d=1,miu(d)=1;

　　若d=$P_{1}P_{2}.......P_{n}$，则miu(d)=$(-1)^{k}$;

　　其他情况下miu(d)=0.

　　我们这道题使用第二种形态。

　　我们设F(n)为gcd(x,y)==n的公倍数的x，y对数，f(n)为gcd(x,y)==n的x，y对数。

　　则有$F(n)=sumlimits_{n|d}^{}f(d)$

　　根据莫比乌斯反演得到$f(n)=sumlimits_{n|d}^{}miu(frac{d}{n})F(d)$

　　$F(d)=frac{n}{d}frac{m}{d}$显然

　　且本题中我们要求的是f(1)

　　那么原式化为$f(1)=sumlimits_{i=1}^{min(n,m)}miu(i)frac{n}{i}frac{m}{i}$

　　那么本题我们做完了吗？答案明显是否定的。

　　因为你直接for一遍i会超时。

　　观察到for i in 1~n　有一段区间使得n/i的取值是相同的

　　而且这个取值最多只有$sqrt[]{n}$种

　　所以应用数论的分块优化

　　贴上代码

　　

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>

using namespace std;

inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}

long long miu[500050];
long long prime[500050],tot;
bool f[600600];

long long count(long long n,long long m){
    long long top=min(n,m);long long ans=0;
    long long x=1;
    while(x<=top){
        long long y=min(n/(n/x),m/(m/x));
        ans+=(long long)(miu[y]-miu[x-1])*(n/x)*(m/x);
        x=y+1;
    }
    return ans;
}

int main(){
    miu[1]=1;
    for(long long i=2;i<=60000;++i){
        if(!f[i]){
            prime[++tot]=i;
            miu[i]=-1;
        }
        for(long long j=1;j<=tot&&prime[j]*i<=60000;++j){
            f[i*prime[j]]=1;
            if(i%prime[j])    miu[i*prime[j]]=-miu[i];
            else    break;
        }
    }
    for(long long i=1;i<=60000;++i)    miu[i]+=miu[i-1];
    long long T=read();
    while(T--){
        long long n=read(),m=read(),e=read();
        n/=e;m/=e;
        if(n>m)    swap(n,m);
        printf("%lld
",count(n,m));
    }
    return 0;
}