<更新提示>

<第一次更新>

<正文>

Zap

Description

FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a ，y<=b，并且gcd(x,y)=d。作为FGD的同学，FGD希望得到你的帮助。

Input Format

第一行包含一个正整数n，表示一共有n组询问。（1<=n<= 50000）接下来n行，每行表示一个询问，每行三个 正整数，分别为a,b,d。（1<=d<=a,b<=50000）

Output Format

对于每组询问，输出到输出文件zap.out一个正整数，表示满足条件的整数对数。

Sample Input

2

4 5 2

6 4 3

Sample Output

3

2

解析

按照题意，可以直接设一个数论函数$$f(d)=\sum_{x=1}^a\sum_{y=1}b[gcd(x,y)=d]$$

代表\([1,a],[1,b]\)范围内最大公因数为\(d\)的二元组个数。

可是这个函数好像比较难求，考虑\(Möbius\)反演。我们发现有函数

比较好求。即\(F(n)\)代表\([1,a],[1,b]\)范围内最大公约数为\(n\)倍数的二元组个数，只需满足二元组\((x,y)\)都是\(n\)倍数即可，所以有

然后套\(Möbius\)定理，得到

对于求解\(f(d)\)，有

设\(t=\frac{n}{d}\)，由于\(\lfloor \frac{a}{n} \rfloor\lfloor \frac{b}{n} \rfloor\)在\(n\leq\min(a,b)\)时有值，所以\(1\leq t\leq\frac{\min(a,b)}{d}\)，则

然后就可以求\(f(d)\)的值了，由于系数\(\lfloor \frac{a}{td} \rfloor\lfloor \frac{b}{td} \rfloor\)是下取整形式的，就可以整除分块一下，对每一块相同的部分一起计算一下即可。

\(Code:\)

#include <bits/stdc++.h>

using namespace std;

const int N=60020,Uplim=5e4;

int a,b,k,vis[N],Prime[N],mui[N],cnt,sum[N],ans;

inline void input(void)

{

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

}

inline void sieve(void)

{

    mui[1] = 1;

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

    {

        if (!vis[i])Prime[++cnt] = i , mui[i] = -1;

        for (int j=1;j<=cnt&&i*Prime[j]<=Uplim;j++)

        {

            vis[ i*Prime[j] ] = true;

            if (i%Prime[j]==0)break;

            mui[ i*Prime[j] ] = -mui[i];

        }

    }

}

inline void init(void)

{

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

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

}

inline void solve(void)

{

    ans = 0 , a /= k , b /= k;

    for (int l=1,r;l<=min(a,b);l=r+1)

    {

        r = min( a/(a/l) , b/(b/l) );

        ans += (a/l) * (b/l) * (sum[r]-sum[l-1]);

    }

}

int main(void)

{

    sieve();

    init();

    int T;

    scanf("%d",&T);

    while (T--)

    {

        input();

        solve();

        printf("%d\n",ans);

    }

    return 0;

}

<后记>