原式可以化为 $\displaystyle{\sum_{p \in primes}\sum_{i = 1}^n\sum_{j = 1}^m[(i, j) = p]}$ 注意到,$[(i, j) = p] = [\frac{(i, j)}{p} = 1] = [(\frac{i}{p}, \frac{j}{p}) = 1]$,因此原式进一步化为 $\displaystyle{\sum_{p \in primes}\sum_{i = 1}^n\sum_{j = 1}^m\sum_{d \mid (\frac{i}{p}, \frac{j}{p})}\mu(d)}$ 我们交换求和顺序,有 $\displaystyle{\sum_{p \in primes}\sum_{d = 1}\mu(d)\sum_{i = 1}^n[d \mid \frac{i}{p}]\sum_{j = 1}^m[d \mid \frac{j}{p}]}$ 注意到,$1 \sim \frac{n}{p}$ 中 $d$ 的倍数有 $\left \lfloor \frac{\frac{n}{p}}{d} \right \rfloor = \left \lfloor \frac{n}{dp} \right \rfloor$ 个,因此有 $\displaystyle{\sum_{p \in primes}\sum_{d = 1}^{\min(\frac{n}{p}, \frac{m}{p})}\mu(d) \left \lfloor \frac{n}{dp} \right \rfloor\left \lfloor \frac{m}{dp} \right \rfloor}$ 令 $t = dp$,我们在外层枚举 $t$ $\displaystyle{\sum_{t = 1}^{\min(n, m)} \left \lfloor \frac{n}{t} \right \rfloor\left \lfloor \frac{m}{t} \right \rfloor \sum_{p \in primes, p \mid t} \mu(\frac{t}{p})}$ 我们维护一个 $\mu$ 的前缀和就可以了,具体来说,我们维护一个数组 $S$ ,枚举 $p, t$ ,如果 $p \mid t$ 就令 $S_k \gets S_k + \mu(\frac{t}{p})$,然后接下来就正常的维护前缀和就行了。
注意该题数据规模很大,需要进行一些优化(比如不该开 long long 的地方用 int)。
题目2165 [BZOJ 2820] YY的GCD
AAAAAAAAAA
8
评论
2022-05-08 14:15:39
|
|
给我自己的博客打个广告,关于莫比乌斯反演和整除分块上面有详细的讲解。 首先,我们求简化版问题:求 $\displaystyle{\sum_{i = 1}^n\sum_{j = 1}^m[(i, j) = 1]}$。 利用 莫比乌斯反演 + 整除分块 我们可以用 $O(\sqrt n)$ 的时间复杂度求解。 注意到,$[(i, j) = 1] = \varepsilon((i, j)) = \sum_{d \mid (i, j)}\mu(d)$。因此该题等价于求 $\displaystyle{\sum_{i = 1}^n \sum_{j = 1}^m \sum_{d \mid (i, j)}\mu(d)}$ 交换求和顺序,有 $\displaystyle{\sum_{d = 1}\mu(d)\sum_{i = 1}^n[d \mid i]\sum_{j = 1}^m[d \mid j]}$ 注意到,$1 \sim n$ 中 $d$ 的倍数有 $\lfloor \frac{n}{d} \rfloor$ 个,因此 $\sum_{i = 1}^n[d \mid i] = \lfloor \frac{n}{d} \rfloor$,因此有 $\displaystyle{\sum_{d = 1}^{\min(n, m)} \mu(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor}$ 接下来,就可以用 整除分块 来求解了。
回到本题,我们将和式展开,有 $\begin{align} \sum_{i = a}^n\sum_{j = b}^m[(i, j) = 1] &= \sum_{i = 1}^n\sum_{j = b}^m\sum_{d \mid i, d \mid j}\mu(d) - \sum_{i = 1}^{a - 1}\sum_{j = b}^m\sum_{d \mid i, d \mid j}\mu(d) \\ &= \sum_{i = 1}^n\sum_{j = 1}^m\sum_{d \mid i, d \mid j}\mu(d) - \sum_{i = 1}^n\sum_{j = 1}^{b - 1}\sum_{d \mid i, d \mid j}\mu(d) - \\ & \quad \enspace \sum_{i= 1}^{a - 1}\sum_{j = 1}^m\sum_{d \mid i, d \mid j}\mu(d) + \sum_{i = 1}^{a - 1}\sum_{j = 1}^{b - 1}\sum_{d \mid i, d \mid j}\mu(d) \end{align}$ 于是转化为了四个上面的简化版问题。
实际上,简化版问题也有对应的题目,可以直接水掉。
题目548 [HAOI 2011]问题B
AAAAAAAAAA
8
评论
2022-05-07 12:55:18
|
|
树形dp。 用 $f_{i, 0}$ 表示不选该点时的士兵数,相反,$f_{i, 1}$ 每个边上至少选一个点。 由上面的性质可以得知, 1.当一个点不选时,另一个点就一定要选了。 2.当选一个点时,另一个点可选可不选。 因此,有 $$\begin{cases} \displaystyle{f_{i, 0} = \sum_{j \in \text{Son}(i)}{f_{j, 1}}} \\\displaystyle{f_{i, 1} = \sum_{j \in \text{Son}(i)}{\min(f_{j, 0}, f_{j, 1})}}\end{cases}$$
题目2997 [POJ 1463]战略游戏
A
7
评论
2022-05-04 19:37:23
|
|
给我自己的博客打个广告(没有写过几篇文章)
给定非负整数 $x, y, m, n, L$。 求最小的非负整数 $t$,使得 $x + tm \equiv y + tn \pmod L$
首先,将题目中同余式化为 $ax + by = c$ 的形式: 1. 移项,得 $(x - y) + t(m - n) \equiv 0 \pmod L$,即 $L \mid (x - y) + t(m - n)$ 2. 设 $pL = (x - y) + t(m - n)$,整理,得 $pL + t(n - m) = (x - y)$ 该方程有解当且仅当 $(L, n - m) \mid (x - y)$ 就求出了方程 $pL + t(n - m) = (L, n - m)$ 的特解 $p_0, t_0$。 得到该方程的通解为 $p = \frac{x - y}{d}p_0 + k\frac{n - m}{d}, \quad t = \frac{x - y}{d}t_0 - k\frac{L}{d} \enspace (k \in \mathbb{Z}, \enspace d = (L, n - m))$ 最后,对通解进行一些调整,就得到了最小整数解
题目1677 [POJ 1061] 青蛙的约会
AAAAAAAAAAAAAAAAAAAAA
6
评论
2022-05-04 19:22:22
|
|
我们用 $f_{i,j}$ 表示 满足“前 $i$ 个含 $1$ 的数量不大于 $j$”的数的个数,相当于求组合数 ${i \choose j}$,即 $ f_{i, j} = f_{i-1, j} + f_{i-1, j-1} $ 处理完动态规划的计算之后,我们从第 $n$ 位(即从右开始数第 $n$ 位)开始,如果 “前 $i-1$ 个含 $1$ 的数量不大于 $L$”的数的个数” 大于序数 $I$ (即 $f_{i-1, L} \ge I$),那么我们输出 $0$,否则输出 $1$ (想一想,为什么) 不难理解,如果一个数的位数大于另一个数的位数,那么这个数一定大于另一个数(废话)。 那么前 $i-1$ 既然已经大于序数 $I$ 了,那么答案对应的数一定小于当前位取 $1$ 时候的数,所以当前位取 $0$。反过来同理。 输出完一位之后序数 $I$ 应减去对应的 $f_{i-1, L}$,并且确定完一位是 $1$ 之后,$1$ 的数量 $L$ 也应减一。即 $I \gets I - f_{i-1, L}$, $L \gets L - 1$
题目862 二进制数01串
AAAAAAAAAAAAA
5
评论
2022-04-08 13:45:12
|
|
Pro833 丑数 题解令 $A$ 是所有丑数构成的集合,容易想到,一个丑数是由小于该丑数的一个丑数乘以一个数 $S_i(1 \le i \le K)$ 得来的。 所以,对于一个丑数 $A_i$,枚举 集合 $S$ 和 集合 $A$ (也可以二分,不过速度本来就够快了),找到两个数 $S_i(1 \le i \le K)$ 和 $A_j(1 \le j \le i-1)$,使得 $S_i \cdot A_j > A_{i-1}$,对所有大于 $A_{i-1}$ 的数 $S_i(1 \le i \le K) \cdot A_j(1 \le j \le i-1)$,找到一个最小的数,赋值于 $A_i$。 即 $A_i \gets \min(S_i \cdot A_j)$,其中,$1 \le i \le K,1 \le j \le i-1$ 最后,第 $N$ 个丑数就是 $A_N$
题目833 丑数
AAAAAAAAAAAA
6
评论
2022-03-28 19:24:07
|