Description

给定 \(N, M\)，求 \(1 \leq x \leq N\)，\(1 \leq y \leq M\) 且 \(\gcd(x, y)\) 为质数的 \((x, y)\) 有多少对。\(T = 10^4\)，\(N, M \leq 10^7\)。

Solution

首先按套路推导出

\[ans=\sum_d \lfloor \frac N d \rfloor \lfloor \frac M d \rfloor \sum_{p|d} \mu(\frac d p) \]

设

\[a(d)=\sum_{p|d} \mu(\frac d p) \]

于是

\[ans=\sum_d \lfloor \frac N d \rfloor \lfloor \frac M d \rfloor a(d) \]

便可以整除分块计算。关键在于如何预处理出 \(a(d)\)。

在预处理完 \(\mu\) 后，对于每一个 \(p\)，枚举 \(j=1,2,3,\dots\)，将 \(\mu(j)\) 加到 \(a(pj)\) 上即可，这部分的时间复杂度根据调和级数，为 \(O(n \log n)\)。由于对于各组数据，\(a(d)\) 的预处理是公共的，只需要在所有询问之前做一次即可。