前置芝士
莫比乌斯函数:
$$ \mu(n) = \begin{cases} 1 & n = 1 \\\ 0 & n\text{含有平方因子} \\\ (-1)^k & k\text{为}n\text{的本质不同质因子个数} \end{cases} $$
莫反证明中要用到的莫比乌斯函数重要性质:
$$ \sum_{d|n} \mu(d) = \begin{cases} 1 & n = 1 \\\ 0 & n\ne 1 \end{cases} $$
简单证明:
设 $n=\prod\limits_{i=1}^kp_i^{c_i}, n’=\prod\limits_{i=1}^kp_i$
则 $\sum\limits_{d|n}\mu(d) = \sum\limits_{d|n’}\mu(d) = \sum\limits_{i=0}^k C_k^i \cdot (-1)^i = (1 + (-1))^k$ (组合数学:k个质因子的选法 + 二项式定理)
故该式子当且仅当 $n=1$ 时,$\sum\limits_{d|1} \mu(d) = \mu(1) = 1$;否则为 $0$
引理1
$$ \forall a,b,c\in Z,有 \bigg\lfloor \frac{a}{bc} \bigg\rfloor = \bigg\lfloor \frac{\lfloor \frac{a}{b} \rfloor}{c} \bigg\rfloor $$
简单证明:
$$ \frac{a}{b} = \bigg\lfloor\frac{a}{b}\bigg\rfloor + r\quad(0\le r\lt1)\\\ \bigg\lfloor\frac{a}{bc}\bigg\rfloor = \bigg\lfloor\frac{a}{b} \cdot \frac{1}{c} \bigg\rfloor = \bigg\lfloor \frac{\Big(\lfloor \frac{a}{b} \rfloor + r\Big)}{c} \bigg\rfloor = \bigg\lfloor \frac{\lfloor \frac{a}{b} \rfloor}{c} + \frac{r}{c} \bigg\rfloor = \bigg\lfloor \frac{\lfloor \frac{a}{b} \rfloor}{c} \bigg\rfloor $$
引理2
$$ \forall n\in N_+,则 \bigg|\left\{\lfloor{\frac{n}{d}}\rfloor ~|~ d\in N_+,d \le n \right\} \bigg| \le \lfloor{2\sqrt{n}}\rfloor $$
简单证明:
对于所有的 $d\le\lfloor{\sqrt{n}}\rfloor$,$\lfloor{\frac{n}{d}}\rfloor$ 至多有 $\lfloor\sqrt{n}\rfloor$ 种取值
对于所有的 $d\gt\lfloor{\sqrt{n}}\rfloor$,则 $\lfloor{\frac{n}{d}}\rfloor$,至多有 $\lfloor\sqrt{n}\rfloor$ 种取值
故加起来至多有 $\lfloor2\sqrt{n}\rfloor$ 种取值
数论分块
考虑含有 $\lfloor{\frac{n}{i}}\rfloor$ 的求和式子($n$ 为常数),对于任意 $i(i\le n)$,找出一个最大的 $j$,$s.t. \lfloor{\frac{n}{i}}\rfloor = \lfloor{\frac{n}{j}}\rfloor$
此时 $j = \Big\lfloor{\dfrac{n}{\lfloor{\frac{n}{i}}\rfloor}}\Big\rfloor$
简单证明:
$$ \begin{align} \lfloor{\frac{n}{i}}\rfloor &\le \frac{n}{i} \\\ {\frac{n}{\lfloor{\frac{n}{i}}\rfloor}} &\ge \frac{n}{\frac{n}{i}} \\\ \bigg\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\bigg\rfloor &\ge \bigg\lfloor\frac{n}{\frac{n}{i}}\bigg\rfloor = \lfloor{i}\rfloor = i \\\ j = \bigg\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\bigg\rfloor &\ge i \end{align} $$
已经证明了 $i \le j \le n$,故证明命题现还需证明: 当 $\lfloor{\frac{n}{i}}\rfloor = \lfloor{\frac{n}{j}}\rfloor$ 时,$j_{max}=\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor$
$$ \begin{align} \lfloor{\frac{n}{i}}\rfloor &= \lfloor{\frac{n}{j}}\rfloor \\\ \lfloor{\frac{n}{i}}\rfloor &\le \frac{n}{j} \lt \lfloor{\frac{n}{i}}\rfloor + 1 \quad(常用不等式:\lfloor a \rfloor \le a \lt \lfloor a \rfloor + 1)\\\ \frac{1}{\lfloor{\frac{n}{i}}\rfloor} &\ge \frac{j}{n} \gt \frac{1}{\lfloor{\frac{n}{i}}\rfloor + 1} \quad(取倒数)\\\ \frac{n}{\lfloor{\frac{n}{i}}\rfloor + 1} &\lt j \le \frac{n}{\lfloor{\frac{n}{i}}\rfloor} \end{align} $$
故 $j_{max} = \bigg\lfloor{\dfrac{n}{\lfloor{\frac{n}{i}}\rfloor}}\bigg\rfloor$
莫比乌斯反演
设 $f(n),g(n)$ 为两个数论函数
如果有 $F(n) = \sum\limits_{d|n}f(d)$,那么有 $f(n) = \sum\limits_{d|n}\mu(d)F(\dfrac{n}{d})$
如果有 $F(n) = \sum\limits_{n|d}f(d)$,那么有 $f(n) = \sum\limits_{n|d}\mu(\dfrac{d}{n})F(d)$
一式证明
$$ \begin{align} \sum_{d|n}\mu(d)F(\frac{n}{d}) &= \sum_{d|n}\mu(d)\sum_{i~|\frac{n}{d}}f(i) \\\ &= \sum_{i|n} f(i) \sum_{d~|\frac{n}{i}}\mu(d) &\bigg(i~|\frac{n}{d} \Rightarrow id|n \Rightarrow d~| \frac{n}{i}\bigg)\\\ &= f(n) \end{align} $$
二式证明
$$ \begin{align} \sum_{n|d}\mu(\frac{d}{n})F(d) &= \sum_{n|d}\mu(\frac{d}{n})\sum_{d|i}f(i) \\\ &= \sum_{n|i}f(i)\sum_{\frac{d}{n} | \frac{i}{n}} \mu(\frac{d}{n}) &\bigg(d | i \Rightarrow \frac{d}{n} | \frac{i}{n}\bigg) \\\ &= \sum_{n|i}f(i)\sum_{d’~| \frac{i}{n}} \mu(d’) \\\ &= f(n) \end{align} $$
这里 y总 证明中用到的 交换求和次序
可以类比 二重积分 在离散情况下 交换积分次序 的手段,会帮助理解
不过 二重积分 是在连续的情况下,因此画出 积分区域 穿个线就好了
而离散情况下,精准的找出每个点,就需要用 整除的性质 ,推推公式 了
本题分析
本题可以用 容斥原理 来做,也可以套 莫比乌斯反演
首先我们利用 前缀和差分思想,先把问题简化,如下图所示:
这样我们的问题就转化成求 $0\le x\le a, 0\le y\le b \text{,且} gcd(x,y) = k$ 的数对个数,即 $\sum\limits_{i=1}^a \sum\limits_{j=1}^b \Big[{(i,j) = n}\Big]$
考虑设函数 $F(n) = \sum\limits_{i=1}^a\sum\limits_{j=1}^b \Big[n ~|~ (i, j)\Big]$,$f(n) = \sum\limits_{i=1}^a \sum\limits_{j=1}^b \Big[{(i,j) = n}\Big]$
在这里,我们先把 $F(n)$ 化简出来,方便后面套莫反计算。
经过观察发现,$F(n) = \sum\limits_{i=1}^a\sum\limits_{j=1}^b \Big[n ~|~ (i, j)\Big]$ 枚举的是满足 $gcd$ 是 $n$ 的倍数的数对
而 $[1, a]$ 上,是 $n$ 的倍数的数的个数有 $\lfloor{\frac{a}{n}}\rfloor$; $[1, b]$ 上,是 $n$ 的倍数的数的个数有 $\lfloor{\frac{b}{n}}\rfloor$
用组合数乘法原理乘起来,得到 $F(n) = \lfloor{\frac{a}{n}}\rfloor \cdot \lfloor{\frac{b}{n}}\rfloor$
再由 $F(n) = \sum\limits_{n~|~d}f(d) $ ,套莫反可得: $ f(n) = \sum\limits_{n~|~d}\mu(\frac{d}{n})F(d) = \sum\limits_{n~|~d}\mu(\frac{d}{n}) \cdot \lfloor{\frac{a}{d}}\rfloor \cdot \lfloor{\frac{b}{d}}\rfloor$
为了方便观察,我们把 $\frac{d}{n}$ 进行换元,令 $\frac{d}{n} = d’$,则原式 $= \sum\limits_{d’}\mu(d’) \cdot \lfloor{\frac{a}{d’n}}\rfloor \cdot \lfloor{\frac{b}{d’n}}\rfloor$
该式中,唯有一个变量 $d’$,故我们把剩余的常量进行统一:令 $\frac{a}{n}=a’, \frac{b}{n}=b’$
于是有:$\sum\limits_{d’}\mu(d’) \cdot \lfloor{\frac{a’}{d’}}\rfloor \cdot \lfloor{\frac{b’}{d’}}\rfloor$
因此我们只需枚举 倍数 $d’$,然后用上文提到的 $数论分块$ 来求对应每个 $d’$ 的表达式的值即可
这里倍数只需枚举到 $min(a’, b’)$ 即可,如果大于任意一个值,代入表达式值都为 $0$
时间复杂度:$O(n\sqrt{n})$
Code
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 50010;
int T, a, b, c, d, k;
int primes[N], cnt, mu[N], smu[N];
bool st[N];
void prework() //预处理莫比乌斯函数和前缀和(分块计算时要用到区间和)
{
mu[1] = 1;
for (int i = 2; i < N; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i, mu[i] = -1;
for (int j = 0; primes[j] * i < N; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
mu[primes[j] * i] = -mu[i];
}
}
for (int i = 1; i < N; i ++ ) smu[i] = smu[i - 1] + mu[i];
}
int g(int i, int n) //数论分块的右端点
{
return n / (n / i);
}
LL f(int a, int b)
{
a = a / k, b = b / k; //对应到推公式里的a',b'换元
LL res = 0;
int n = min(a, b);
for (int l = 1, r; l <= n; l = r + 1)
{
r = min({n, g(l, a), g(l, b)});
int _d = l;
res += (LL) (smu[r] - smu[l - 1]) * (a / _d) * (b / _d);
}
return res;
}
void solve()
{
scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
printf("%lld\n", f(b, d) - f(a - 1, d) - f(b, c - 1) + f(a - 1, c - 1));
}
int main()
{
prework();
scanf("%d", &T);
while (T -- ) solve();
return 0;
}
Code (容斥原理)
提高课链接:AcWing 215. 破译密码(算法提高课)
数论大佬%%%%
hhh,想到一块去了,我也是刚开始就想到了二重积分的交换次序
👍
QwQ
👍
QwQ
质量太高了!!!
QwQ