Description：

求 $\begin{align}\sum_{i=1}^a\sum_{j=1}^b[gcd(i,j)=d]\end{align}$

$1\le T \le 50000$ $1\le d \le a,b \le 50000$

Solution：

$\begin{align}\sum_{i=1}^a\sum_{j=1}^b[gcd(i,j)=d]\end{align}$

$=\begin{align}\sum_{i=1}^{\lfloor\frac a d\rfloor}\sum_{j=1}^{\lfloor\frac b d\rfloor}\varepsilon(gcd(i,j))\end{align}$

$=\begin{align}\sum_{i=1}^{\lfloor\frac a d\rfloor}\sum_{j=1}^{\lfloor\frac b d\rfloor}\sum_{d|gcd(i,j)}\mu(d)\end{align}$

设 $n=\lfloor\frac a d\rfloor$ ， $m=\lfloor\frac b d\rfloor$ ，交换求和号，得：

$\begin{align}原式=\sum\mu(d)\lfloor\frac n d\rfloor\lfloor\frac m d\rfloor\end{align}$

预处理 $\mu$ 前缀和 $+$ 除法分块求和即可

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int testcases;

#define MAXN 500010

int prime[MAXN],tot = 0;

bool isprime[MAXN + 1];

typedef long long ll;

ll mu[MAXN],sum[MAXN];

void init()

{

    for(int i = 2;i <= MAXN;++i)isprime[i] = true;

    mu[1] = 1;

    for(int i = 2;i <= MAXN;++i)

    {

        if(isprime[i])

        {

            prime[++tot] = i;

            mu[i] = -1;

        }

        for(int j = 1;j <= tot && i * prime[j] <= MAXN;++j)

        {

            isprime[i * prime[j]] = false;

            if(i % prime[j] == 0)

            {

                mu[i * prime[j]] = 0;

                break;

            }

            else

            {

                mu[i * prime[j]] = -1 * mu[i];

            }

        }

    }

    for(int i = 1;i <= MAXN;++i)

    {

        sum[i] = sum[i - 1] + mu[i];

    }

    return;

}

int a,b,d;

ll calc(int n,int m)

{

    ll res = 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));

        res += (sum[r] - sum[l - 1]) * (n / l) * (m / l);

    }

    return res;

}

int main()

{

    init();

    scanf("%d",&testcases);

    for(int i = 1;i <= testcases;++i)

    {

        scanf("%d%d%d",&a,&b,&d);

        printf("%lld\n",calc(a / d,b / d));

    }

    return 0;

}