问题描述： 对于给定的整数$a，b，d$，有多少正整数对$x，y$，满足$x<=a，y<=b$并且$gcd(x,y)=d$
输入： 第一行包含一个正整数$n$，表示一共有$n$组数据$（1<=n<= 50000）$ 接下来$n$行，每行表示一个询问。每行三个正整数，分别为$a,b,d$（$1<=d<=a,b<=50000$）
输出： 对于每组询问，输出一个正整数，表示满足条件的整数对数
思路： 这是一个莫比乌斯反演的模版题，莫比乌斯反演虽然听起来很高级但内容还是比较好理解的。
首先是莫比乌斯函数$\mu(n)$，这是一个表示容斥系数的函数。它的定义是这样的：当n有相等的质因子$\mu(n)=0$；当n没有相等质因子且质因子个数为偶数$\mu(n)=1$；当$n$没有相等质因子且质因子个数为奇数$\mu(n)=-1$。
然后关于莫比乌斯反演有下面两个形式：我们设存在两个函数$F(n), f(n)$
形式一：如果满足条件 那么就有： 形式二：如果满足条件 那么就有： 关于证明，我这么菜自然是不懂的。
对于这道题，设$x=\lfloor a/d\rfloor$， $y=\lfloor b/d \rfloor$。显然可以将题目转化为求这样一个式子： 然后我们设$f(n)$为在范围内$gcd(i,j)=n$的的个数，设$F(n)$为在范围内$n|gcd(i,j)$的个数，因此 那么很显然，函数$f(d),F(n)$满足反演的第二种形式且$f(1)$就是我们所求答案。于是利用反演得到：
于是直接计算就是这样的（实测70分）:
1 2 for (int j=1 ; j<=min (a, b); j++) ans+=mob[j]*(a/j)*(b/j);
然后可以发现$a/j, b/j$的取值是一段一段的，所以我们利用数论分块的方法进行优化。数论分块可以看这道题:BZOJ1257 余数之和 ，然后代码是这样的：
1 2 3 4 5 6 for (int l=1 , r; l<=min (a, b); l=r+1 ){ r=min (a/(a/l), b/(b/l)); ans+=(mob[r]-mob[l-1 ])*(a/l)*(b/l); }
代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> #define MAXN 500005 #define LL long long using namespace std;int n, a, b, d, cnt, pri[MAXN], tag[MAXN], mob[MAXN];void init () mob[1 ]=1 ; for (int i=2 ; i<=50000 ; i++) { if (!tag[i]) pri[++cnt]=i, mob[i]=-1 ; for (int j=1 ; j<=cnt && pri[j]*i<=50000 ; j++) { tag[i*pri[j]]=1 ; if (i%pri[j]==0 ) {mob[i*pri[j]]=0 ; break ;} else mob[i*pri[j]]=-mob[i]; } } for (int i=2 ; i<=50000 ; i++) mob[i]+=mob[i-1 ]; } int main () init (); scanf ("%d" , &n); for (int i=1 ; i<=n; i++) { int ans=0 ; scanf ("%d%d%d" , &a, &b, &d); a/=d; b/=d; for (int l=1 , r; l<=min (a, b); l=r+1 ) { r=min (a/(a/l), b/(b/l)); ans+=(mob[r]-mob[l-1 ])*(a/l)*(b/l); } printf ("%dn" , ans); } }