当前位置：首页 > news >正文

Luogu-P3455 [POI 2007] ZAP-Queries

news 2025/9/30 1:42:59

时间限制 \(1.5\,\text{sec}\)
空间限制 \(512\,\text{MB}\)

题目来源洛谷。

题目大意

给定正整数 \(a,\,b,\, d\) ，求在 \(1\leq x \leq a\) 和 \(1\leq y \leq b\) 的限制下满足 \(\gcd(x,\, y) = d\) 的二元组数量。

数据范围

测试集大小 \(1\leq T \leq 5\times 10^4\)
常数 \(1\leq a,\,b,\,d \leq 5\times 10^4\)

分析

事实上，题目要我们求的是

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

的值，这里默认 \(a\leq b\) 。

先令 \(i\leftarrow di\) ，\(j\leftarrow dj\) ，此时

\[\begin{aligned} I &= \sum_{i=1}^{a} \sum_{j=1}^{b}\,[\gcd(i,\, j) = d] \\[1ex]&= \sum_{di=1}^{a} \sum_{dj=1}^{b}\,[\gcd(di,\, dj) = d] \\[1ex]&= \sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}\, [\gcd(i,\, j) = 1]\, . \end{aligned} \]

上面的求和函数是经典的 Möbius 反演的一个推论，于是

\[I = \sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}\,\sum_{x\,|\gcd(i,\, j)} \mu(x)\,, \]

我们更喜欢传统的求和枚举，所以要把对 \(\gcd\) 的约数求和转化成线性求和。注意到 \(x\) 是 \(\gcd(i,\, j)\) 的约数当且仅当 \(x\) 同时是 \(i,\, j\) 的约数，而 \(\gcd(i,\, j) \leq \min\{i,\, j\}\) ，因此

\[\begin{aligned} I &= \sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}\,\sum_{x=1}^{\lfloor \frac{a}{d} \rfloor}\,[d\,|\,i]\cdot [d\,|\,j]\cdot \mu(x)\, \\[1ex] &= \sum_{x=1}^{\lfloor \frac{a}{d} \rfloor}\mu(x)\,\sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\,[d\,|\,i]\,\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}\,[d\,|\,j]\, , \end{aligned} \]

这里求和换序是因为三者的求和函数都是与其它两个变量无关的。

现在观察后两个求和式，它实际上做的是求 \([1,\,m]\) 中 \(d\) 倍数的个数，答案显然是 \(\lfloor \frac{m}{d} \rfloor\)，所以进一步化简得

\[\begin{aligned} I &= \sum_{x=1}^{\lfloor \frac{a}{d} \rfloor}\mu(x)\,\sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\,[d\,|\,i]\,\left\lfloor \dfrac{b}{xd} \right\rfloor \\[1ex]&= \sum_{x=1}^{\lfloor \frac{a}{d} \rfloor}\mu(x)\,\left\lfloor \dfrac{a}{xd} \right\rfloor\left\lfloor \dfrac{b}{xd} \right\rfloor \, . \end{aligned} \]

现在只剩下一个求和了，但是题目有 \(T\) 组测试数据，最坏的时间复杂度是 \(O(T\times \max{a})\)，无法通过，需要进一步优化。

对于含整除的求和式，最自然的想法是数论分块，这里两个整除相乘也是同理——只要每次分块取两个块的最小右端点即可^[1]，这样就把一次求和的复杂度降到了 \(O(\sqrt{a})\)

时间复杂度 \(O(T\sqrt{a})\)

题解

constexpr int MAXN = 5e4 + 10;i64 mu[MAXN], pre[MAXN];
bool not_prime[MAXN];
void euler_sieve(i64 n)
{mu[1] = 1;std::vector<i64> rst;for (i64 i = 2; i < n; i++){if (!not_prime[i]){mu[i] = -1;rst.push_back(i);}for (i64 p : rst){if (p * i > n)break;not_prime[p * i] = true;if (i % p == 0){mu[i * p] = 0;break;}mu[i * p] = -mu[i];}}for (int i = 1; i < n; i++)pre[i] = pre[i - 1] + mu[i];
}void solve(const int &T)
{i64 a, b, d;std::cin >> a >> b >> d;a /= d, b /= d;if (a > b)std::swap(a, b);i64 ans = 0;i64 l = 1, r;while (l <= a){r = std::min(a / (a / l), b / (b / l));// pre[] 是预处理的 mu[] 前缀和ans += (pre[r] - pre[l - 1]) * (a / l) * (b / l);l = r + 1;}std::cout << ans << "\n";
}