破译密码

这个题目和莫比乌斯反演并没有太大关系,只是用了莫比乌斯函数而已,本质就是整数分块+容斥原理.
题目很简单:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d.
这个怎么做呢?我们转化一下,就变成了x'=a/d,y'=b/d.并且gcd(x',y')=1的个数.这个O(n)的做法大家都会吧,但是数据自带5e5的查询,显然NT是过不去的,先讲讲nt做法,就是总数为x'*y'.x'中含有因子2的有x'/2个,同理y'中含有因子2的有y'/2.到了3也是一样的,然后我们会发现这两个的最小公倍数计算了2次,就要减去.以此容斥下去.会发现就是莫比乌斯函数,所以我们可以用线性筛求莫比乌斯函数,然后就是一个公式.

答案就是这个qaq.
然后我们来思考怎么优化这个算法.然后就是个经典的整数分块了.不懂的看视频.hhh.我做的.
https://www.bilibili.com/video/BV19i4y1s7nH
预处理下mubius函数数组,然后前缀以下就好了.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
int sum[N],mob[N];
int st[N],prime[N];
void mobius()
{
    mob[1]=1;int g=0;
    for(int i=2;i<=N-5;i++)
    {
        if(!st[i])  {prime[g++]=i;mob[i]=-1;}
        for(int j=0;prime[j]*i<=(N-5);j++)
        {
            st[prime[j]*i]=1;
            if(i%prime[j]==0)   {mob[prime[j]*i]=0;   break;}
            mob[prime[j]*i]=(-1)*mob[i];
        }
    }
    for(int i=1;i<=N-5;i++)
    {
        sum[i]+=sum[i-1]+mob[i];
    }
}//处理mobius数组和前缀数组

int main()
{
    int T,a,b,d;
    cin>>T;
    mobius();
    while(T--)
    {
        cin>>a>>b>>d;
        //整数分块.
        ll ans=0;
        int x=a/d,y=b/d;
        for(int l=1,r;l<=min(x,y);l=r+1)
        {
            r=min(min(x/(x/l),y/(y/l)),min(x,y));
            ans+=(sum[r]-sum[l-1])*1ll*(x/l)*(y/l);
        }
        cout<<ans<<endl;
    }
    return 0;
}