分析
-
本题中的需要用到知识点:莫比乌斯函数(Mobius函数)。下面给出该函数的定义:
-
对于给定正整数
x
,如果x
可以被质因数分解为$p_1^{\alpha_1} \times p_2^{\alpha_2} \times … \times p_k^{\alpha_k}$,莫比乌斯函数记作$\mu (x)$,则:
$$ \mu (x) = \begin{cases} 0 \quad \quad 至少存在一个\alpha的值大于1 \\\\ 1 \quad \quad 所有\alpha值都为1,且k为偶数 \\\\ -1 \quad \quad 所有\alpha值都为1,且k为奇数 \end{cases} $$
-
那么该函数有什么作用以及如何求解呢?
-
作用如下(存疑?):可以求解
1~N
中和N
互质的数的个数,我们使用$S_{p,q}$表示表示1~N
中和N
存在公因数p
和q
的所有数的集合(其中p、q
都是质数),一共有$\lfloor \frac{N}{p} \rfloor$个数。则1~N
中和N
互质的数的个数为:
$$ N - |S_2| - |S_3| - |S_5| -… + |S_{2,3}| + |S_{3,5}| + … - |S_{2,3,5}| -… $$
观察可以发现,上式中除了N
之外的的其他项的系数就是莫比乌斯函数,因此上式可以改写成:
$$
N - \sum \mu (p) \times |S_p|
$$
- 如何求解
1~N
中每个数对应的莫比乌斯函数值呢?可以在质数线性筛法中求解,代码以及分析如下:
// 线性选法,时间复杂度:O(n)
void get_primes(int n) {
mobius[1] = 0;
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[cnt++] = i;
mobius[i] = -1; // i本身就是质数,k为奇数
}
for (int j = 0; primes[j] <= n / i; j++) {
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0) {
mobius[t] = 0; // t至少存在两个质因子primes[j]
break;
}
// mobius[i] = 0 时, mobius[t]也为0
// mobius[i] != 0 时, 此时t比i多一个i质因数分解中不存在的质数, mobius[t]和mobius[i]异号
mobius[t] = mobius[i] * -1;
}
}
}
-
现在我们考虑本题如何求解,问题是给定我们
a、b、d
,我们需要计算数对的数量,这些数对(x, y)
需要满足:$1 \le x \le a, 1 \le y \le b$且gcd(x, y)==d
。 -
上述问题等价于:$1 \le x’ \le \lfloor \frac{a}{d} \rfloor, 1 \le y’ \le \lfloor \frac{b}{d} \rfloor$且
gcd(x', y')==1
的数对的数量。证明也很简单,只需要做一个简单的映射即可,即$x’ = \frac{x}{d}, y’ = \frac{y}{d}$。 -
首先让$a = \lfloor \frac{a}{d} \rfloor, b = \lfloor \frac{b}{d} \rfloor$。
-
现在问题转成了求互质的数的对数,这两个数的范围分别是从
1~a
,和从1~b
。可以使用容斥原理。最后的答案是:
$$ a \times b - \lfloor \frac{a}{2} \rfloor \times \lfloor \frac{b}{2} \rfloor - \lfloor \frac{a}{3} \rfloor \times \lfloor \frac{b}{3} \rfloor + \lfloor + … + \frac{a}{6} \rfloor \times \lfloor \frac{b}{6} \rfloor + ...... $$
其中$\lfloor \frac{a}{2} \rfloor \times \lfloor \frac{b}{2} \rfloor$代表a、b
存在公因数2
的数的对数。上式可以形式化的写成:
$$
\sum _ {i=1} ^ {min(a, b)} \mu (i) \times \lfloor \frac{a}{i} \rfloor \times \lfloor \frac{b}{i} \rfloor
$$
-
根据上式我们可以看出每次查询的时间复杂度是$O(n)$的,因此总体的时间复杂度为$O(n^2)$,
n
最大为50000
,会超时。因此需要优化。 -
我们考虑对于给定正整数
n
,考虑$\lfloor \frac{n}{1} \rfloor, \lfloor \frac{n}{2} \rfloor,\lfloor \frac{n}{3} \rfloor, …,\lfloor \frac{n}{n} \rfloor$中实际存在多少不同的数据,另外如何求解出这些数据的个数。 -
存在多少不同的数据:
-
实际上上述数据的个数不超过$2 \times \sqrt n$个,这是因为我们可以将数据分为两组:
(1)$\lfloor \frac{n}{1} \rfloor, \lfloor \frac{n}{2} \rfloor, …,\lfloor \frac{n}{\sqrt n} \rfloor$;
(2)$\lfloor \frac{n}{\sqrt n + 1} \rfloor, \lfloor \frac{n}{\sqrt n +2} \rfloor, …,\lfloor \frac{n}{n} \rfloor$。
-
第(1)部分只有$\sqrt n$项;第(2)部分虽然项数很多,但是数值都是小于$\sqrt n$的,因此最多有$\sqrt n$项;因此不同的数据的个数不超过$2 \times \sqrt n$个。
-
如何求解出这些数据的个数:
-
我们首先考虑如下问题:对于
n
,给定我们一个小于等于n
的正整数x
,我们希望找到值等于$\lfloor \frac{n}{x} \rfloor$且最大的一个数y
满足$\lfloor \frac{n}{x} \rfloor = \lfloor \frac{n}{y} \rfloor$,我们可已看出y
是x
的函数,令$g(x)=y$,例如给定n=24, x=9
,则g(x)=12
,因为$\lfloor \frac{24}{9} \rfloor = \lfloor \frac{24}{12} \rfloor$,且12
是最大的一个。 -
g(x)
的形式化定义如下:$\lfloor \frac{n}{x} \rfloor = \lfloor \frac{n}{g(x)} \rfloor$且$\lfloor \frac{n}{x} \rfloor > \lfloor \frac{n}{g(x) + 1} \rfloor$。这里的g(x)
是由公式解的,如下:
$$ g(x) = \lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor $$
-
我们可以证明
g(x)
是满足形式化定义中的两个式子的,首先证明:$\lfloor \frac{n}{x} \rfloor = \lfloor \frac{n}{g(x)} \rfloor$。(证明方式:A>=B, A<=B
,则A==B
) -
根据
g(x)
的表达式,我们可以推出:
$$ g(x) = \lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor >= \lfloor \frac{n}{\frac{n}{x}} \rfloor = x $$
因此有:
$$
\lfloor \frac{n}{x} \rfloor <= \lfloor \frac{n}{g(x)} \rfloor \quad (1)
$$
将g(x)
带入$\lfloor \frac{n}{g(x)} \rfloor$,可以得到:
$$
\lfloor \frac{n}{g(x)} \rfloor = \lfloor \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor} \rfloor >= \lfloor \frac{n}{\frac{n}{\lfloor \frac{n}{x} \rfloor}} \rfloor = \lfloor \frac{n}{x} \rfloor \quad (2)
$$
因此(1)(2)式可知:$\lfloor \frac{n}{x} \rfloor = \lfloor \frac{n}{g(x)} \rfloor$。
-
下面接着证明形式化定义的第二个式子:$\lfloor \frac{n}{x} \rfloor > \lfloor \frac{n}{g(x) + 1} \rfloor$。
-
令$n = k \times x + r, 0 \le r < x$(对
x
求带余除法),则等价于证明下式(此时$g(x) = \lfloor \frac{n}{k} \rfloor$):
$$ k > \lfloor \frac{n}{\lfloor \frac{n}{k} \rfloor + 1} \rfloor $$
等价于证明:
$$
k \times (\lfloor \frac{n}{k} \rfloor + 1) > n
$$
令$n = p \times k + q, 0 \le q < k$(对k
求带余除法),带入上式可以得到:
$$
k \times (p + 1) > p \times k + q \iff k > q
$$
因此第二个式子也是成立的。
- 有了上述理论之后,我们就可以快速求解出刚开始推出来的式子:
$$ \sum _ {i=1} ^ {min(a, b)} \mu (i) \times \lfloor \frac{a}{i} \rfloor \times \lfloor \frac{b}{i} \rfloor $$
-
$\lfloor \frac{a}{i} \rfloor \times \lfloor \frac{b}{i} \rfloor$对应的序列有很多值都是相同的,计算一次就行,假设值记为
t
,对应的区间假设为[l, r]
,然后让t
乘以$\mu(l)+\mu(l+1)+…+\mu(r)$即可求出该段中的和,$\mu(l)+\mu(l+1)+…+\mu(r)$可以使用前缀和求解。 -
时间复杂度为$O(n \times \sqrt n)$,
n
次询问,每次询问有不多于$2 \times \sqrt n$段数据相加。
代码
- C++
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 50010;
int primes[N], cnt;
bool st[N];
int mobius[N], sum[N]; // sum是mobius的前缀和
// 线性筛法求莫比乌斯函数
void init(int n) {
mobius[1] = 1;
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[cnt++] = i;
mobius[i] = -1;
}
for (int j = 0; primes[j] * i <= n; j++) {
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0) {
mobius[t] = 0;
break;
}
mobius[t] = mobius[i] * -1;
}
}
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + mobius[i];
}
int main() {
init(N - 1);
int T;
scanf("%d", &T);
while (T--) {
int a, b, d;
scanf("%d%d%d", &a, &b, &d);
a /= d, b /= d;
int n = min(a, b);
LL res = 0;
for (int l = 1, r; l <= n; l = r + 1) {
r = min(n, min(a / (a / l), b / (b / l))); // 下次跳到的位置应该是r+1
res += (sum[r] - sum[l - 1]) * (LL) (a / l) * (b / l);
}
printf("%lld\n", res);
}
return 0;
}
写的这么详细竟然没人膜一个,我先 %%% 为敬 orz orz