P3455 [POI 2007] ZAP-Queries

这道题就是求：

$\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(x,y)=d]$

• $1\le d\le a,b\le 50000$。

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

结合莫比乌斯反演：

$g(n)=\sum_{n|k}f(k)$

$f(n)=\sum_{n|k}\mu(\frac{k}{n})g(k)$

我们构造：

$g(n)=\sum_{n|d}f(d)=\lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor$

这个式子可以直接根据定义去理解，就是所有是 $n$ 的倍数的 $i$ 和所有是 $n$ 的倍数的 $j$ 进行组合。

然后我们根据莫比乌斯反演的式子：

$f(d)=\sum_{d|k}\mu(\frac{k}{d})g(k)$

然后答案就是：

$\sum_{d|k}\mu(\frac{k}{d})g(k)$

$\sum_{d|k}\mu(\frac{k}{d})\lfloor\frac{a}{k}\rfloor\lfloor\frac{b}{k}\rfloor$

令 $\frac{k}{d}$ 为 $t$（整数）。

$\sum_{t=1}^{min(\frac{a}{k},\frac{b}{k})}\mu(t)\lfloor\frac{a}{td}\rfloor\lfloor\frac{b}{td}\rfloor$

然后现在是 $O(n)$ 的，需要继续优化。

然后这个式子就是整除分块的，所以我们使用整除分块。

什么是整除分块？

先看这样一个式子：

我们发现如果暴力是 $O(n)$ 的，很慢，所以尝试优化。

我们发现这是数学题，尝试打表，对于 $n=10$。

10
5
3
2
2
1
1
1
1
1

观察一下，我们可以发现这种式子带有很多的相同数字，我们只需要把每一个数字的值乘上个数相加就行了

。稍微想想，会发现：

• 当 $i \le \sqrt{n}$ 时，$i$ 本身只有 $\sqrt{n}$ 种可能，因此 $\lfloor \frac{n}{i} \rfloor$ 至多对应 $\sqrt{n}$ 个不同的值。
• 当 $i > \sqrt{n}$ 时，$\lfloor \frac{n}{i} \rfloor < \sqrt{n}$，即其取值只能是 $1, 2, \dots, \lfloor \sqrt{n} \rfloor$，同样不超过 $\sqrt{n}$ 种。

所以复杂度就是根号级别的了。

具体的写法就对于 $l$，求出数字相同的区间 $[l,r]$，然后处理完这个区间之后 $l=r+1$，进入下一个区间。

回过头来，我们了解了整除分块的思想，看看刚刚的式子：

$\sum_{t=1}^{\min(\frac{a}{k},\frac{b}{k})}\mu(t)\lfloor\frac{a}{td}\rfloor\lfloor\frac{b}{td}\rfloor$

我们只需要找到 $\lfloor\frac{a}{td}\rfloor$ 和 $\lfloor\frac{b}{td}\rfloor$ 都相同的区间即可。

void solve(){
	int n=min(a/d,b/d);
	int ans=0;
	for(int l=1,r=0;l<=n;l=r+1){//l <- t 
		r=min((a/d)/(int)(a/l/d),(b/d)/(int)(b/l/d));
		ans+=(sum[r]-sum[l-1])*((a/l/d)*(b/l/d));
	}
	cout<<ans<<endl;
}