LUOGU 3455
Description
FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数和，有多少正整数对，满足，并且。作为FGD的同学，FGD希望得到你的帮助。

Input Format
第一行一个正整数，表示询问组数。
接下来行，每行个正整数，含义如题目所示意。

Output Format
对于每个询问输出一行表示答案。

Sample Input

2
4 5 2
6 4 3

Output Format

3
2

Constraints
对于%的数据，满足。

CCYOS
这是一道莫比乌斯反演的板子题。

1. 前置技能

符号	含义
	被整除
	质数集合
	的不同质因数个数
	内与n互质的数的个数显然n和本身不互质
	莫比乌斯函数，详见下文
	狄利克雷卷积单位元
	对于任意，，乘法单位元
	对于任意
	命题成立，；反之为

概念	含义
数论函数	定义域为全体正整数，值域为复数域子集的函数。
积性函数	若，则
完全积性函数	对于任意，都有

2. 莫比乌斯函数
   其中，表示每一个质因数的次数。
   一个重要的性质

证明如下：
1）当时:显然。可枚举的约数只有，则原式 = = = 。
2） 当时:显然此时，。则约数因为，所以。不难看出，枚举的约数，即枚举取的质因数的乘积即可。根据的定义，有根据二项式定理构造可得即此时原式恒为0。
3）定义域内其他情况:即在第二种情况上添加，据定义有。所以此时原式恒为0。
证毕。

get_mu函数的写法

inline void get_mu(int N){
    miu[1] = 1;//初始化
    for(int i = 2;i <= N;++i){//从2开始
        if(!vis[i])prime[++cnt] = i,miu[i] = -1;//标记质数，质数只有两个约数所以质数的miu值一定是-1
        for(int j = 1;j <= cnt&&prime[j] * i <= N;++j){
            vis[i * prime[j]] = 1;//标记合数
            if(!(i % prime[j]))break;//避免标记到存在ki >= 2的数
            else miu[i * prime[j]] = -miu[i];//多了一个质因数,(-1)^k要取相反
        }
    }
    for(int i = 1;i <= N;++i)sum[i] = sum[i - 1] + miu[i];//前缀和便于计算
}

3. 狄利克雷卷积
   满足交换率，结合率，分配律。
   两个积性函数的卷积一定是积性函数。

4. 
   单位元的是满足 f * e = f的函数，当 e = [n = 1]时，这个条件成立，所以这种定义是满足条件的定义之一。而且很好记。

证明：
证毕

5. 欧拉函数
   一个重要的性质
   

证明：
咕咕咕。不会证。

推论
1）

证明：
证毕

2）

证明：
由5.1.推出狄利克雷卷积满足结合律，所以由4.可得证毕

6. 莫比乌斯反演
   当必然有假设和结果互换，此仍然为真命题。

证明如下：
构造转化假设，有
则转为证明：若则。
与5.2.证明相类似，由假设得到由4.得
反之证若则: 证毕

一些常见的推论
1）

证明:
由莫比乌斯函数的性质可得代入原式可得因为，所以，故考虑先枚举，再枚举，可得把后面一段废话化简得证毕

2）

证明：
将原式转化为依照6.1.的证明。
证毕

3）

证明：
由5.1可得代入原式中可得依照6.1.证明。
证毕

一般做法
根据题意列出算式。
列出一个可以反演的方程。
反复化简，向函数靠拢。
计算。

小技巧：整除分块
通过观（da）察（biao）发现，在处理的过程中，会出现很多相同的结果，而且这些结果呈块状分布。进一步观（da）察（biao），会发现对于每一个结果相同的块，当前位置为,这个块的结束位置为。
那么整除分块的代码就很好写了：

for(int l = 1,r;l <= n;l = r + 1){
  r = n/(n/l);  
  一些操作;
}

在GC的帮助下找到了理解这个问题的另一个思路：LUOGU 1403 感谢！！！

code

#include<bits/stdc++.h>
using namespace std;

#define mxn 50005
int N,cnt;
int sum[mxn],prime[mxn],vis[mxn],miu[mxn];

inline int read(){
    int ret = 0,fl = 1;
    char c = getchar();
    for(;!isdigit(c)&&c != '-';c = getchar())if(c == '-')fl = 0;
    for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
    return fl ? ret : -ret;
}

inline void get_mu(int N){
    miu[1] = 1;
    for(int i = 2;i <= N;++i){
        if(!vis[i])prime[++cnt] = i,miu[i] = -1;
        for(int j = 1;j <= cnt&&prime[j] * i <= N;++j){
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))break;
            else miu[i * prime[j]] = -miu[i];
        }
    }
    for(int i = 1;i <= N;++i)sum[i] = sum[i - 1] + miu[i];
}

int main(){
    N = read();
    get_mu(50000);
    for(int i = 1;i <= N;++i){
        int a,b,k;
        long long ans = 0;
        a = read();b = read();k = read();
        int limit = min(a,b);
        for(int l = 1,r;l <= limit;l = r + 1){
            r = min(a/(a/l),b/(b/l));
            ans += 1ll * (a/(l * k)) * (b/(l * k)) * (sum[r] - sum[l - 1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

参考文档

• 知乎-莫比乌斯反演
• 数论初步