问题描述：
对于给定的整数$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);
}
}
|