$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

莫比乌斯函数：

$n={p_1}^{a_1}\cdot {p_2}^{a_2}\cdot …\cdot {p_k}^{a_k}$

$\mu(n)=\begin{cases}0&存在\ a_i>1\\\\1&a_i=1且\ k\bmod 2=0\\\\-1&a_i=1且\ k\bmod 2=1\end{cases}$

思路：

$题意：1\le x\le a，1\le y\le b，求\gcd(x,y)=d的方案数$

$转化：1\le x’\le \left\lfloor\dfrac{a}{d}\right\rfloor，1\le y’\le \left\lfloor\dfrac{b}{d}\right\rfloor，求\gcd(x’,y’)=1的方案数$

$令a=\left\lfloor\dfrac{a}{d}\right\rfloor，b=\left\lfloor\dfrac{b}{d}\right\rfloor$

$\begin{aligned}合法方案 & = 总方案-不合法方案 \\\\ & =a\cdot b-(S_1\cup S_2\cup… \cup S_n)\\\\ & = a\cdot b-\left\lfloor\dfrac{a}{2}\right\rfloor\cdot \left\lfloor\dfrac{b}{2}\right\rfloor-\left\lfloor\dfrac{a}{3}\right\rfloor\cdot \left\lfloor\dfrac{b}{3}\right\rfloor-\left\lfloor\dfrac{a}{5}\right\rfloor\cdot \left\lfloor\dfrac{b}{5}\right\rfloor-…\\\\&\ \ \ \ \ \ \ \ \ \ \ \ + \left\lfloor\dfrac{a}{6}\right\rfloor\cdot \left\lfloor\dfrac{b}{6}\right\rfloor+\left\lfloor\dfrac{a}{15}\right\rfloor\cdot \left\lfloor\dfrac{b}{15}\right\rfloor+\left\lfloor\dfrac{a}{30}\right\rfloor\cdot \left\lfloor\dfrac{b}{30}\right\rfloor+…\\\\&\ \ \ \ \ \ \ \ \ \ \ \ -\left\lfloor\dfrac{a}{30}\right\rfloor\cdot \left\lfloor\dfrac{b}{30}\right\rfloor-…\end{aligned}$

$g(x)=\left\lfloor\dfrac{a}{\left\lfloor\dfrac{a}{x}\right\rfloor}\right\rfloor$

$例如：\left\lfloor\dfrac{24}{9}\right\rfloor=\left\lfloor\dfrac{24}{10}\right\rfloor=\left\lfloor\dfrac{24}{11}\right\rfloor=\left\lfloor\dfrac{24}{12}\right\rfloor=2，因此，g(9)=12$

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 50010;

int primes[N],cnt;
bool st[N];
int mobius[N],sum[N];

//线性筛莫比乌斯函数
void init(int n)
{
    mobius[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) 
        {
            primes[cnt++]=i;
            mobius[i]=-1; //只有一个质数
        }
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0)
            {
                mobius[primes[j]*i]=0; //某个质因子数大于一
                break;
            }
            mobius[primes[j]*i]=mobius[i]*-1;
        }
    }

    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+mobius[i];
}

int main()
{
    init(N-1);

    int T;
    cin>>T;
    while(T--)
    {
        int a,b,d;
        cin>>a>>b>>d;
        a/=d,b/=d;

        int n=min(a,b);
        LL res=0;
        for(int l=1,r;l<=n;l=r+1)
        {
            r=min(a/(a/l),b/(b/l)); //可以跳到的最远距离
            res+=(LL)(sum[r]-sum[l-1])*(a/l)*(b/l); //当 x∈[l,r] 时，(a/x)*(b/x)都是相等的
        }

        cout<<res<<endl;
    }

    return 0;
}