搬这题只是为了庆祝窝洛谷过审的第一篇题解awa

首先这种格式一看就是要用数据结构维护，但我们会发现由于 $a$ 数组和 $k$ 的值都是变化的，普通数据结构几乎难以维护。

遇到这种问题，我们可以尝试往分块或者根号分治上想。

顺着这个思路，考虑寻找一下答案的性质。

发现当 $k \gt \sqrt{N}$ 时，操作时间复杂度最多只有 $O(\sqrt{N})$。

那要是 $k \le \sqrt{N}$ 怎么办？

这个时候 $k$ 已经非常小了，我们可以把 $k \le \sqrt{N}$ 的每一种情况都预处理出来。

在询问时，若 $k \gt \sqrt{N}$ 时，直接暴力模拟，反之直接输出我们预处理的结果就好了。

相当于用空间换时间，二者复杂度均为 $O(N\sqrt{N})$。

根号分治的有趣运用还有很多，这道题基本上相当于模板，还有一道类似的题目 哈希冲突

可以尝试做一做，cb 大佬的题解

看到这道题，最朴素的想法是用 DFS 求解。

显然这样搜出来的状态数量非常庞大，时间复杂度无法承受，考虑换用 DP 遍历所有状态。

这里有两个方法。

法一：(60pts)

设 $f_i$ 表示正整数 $i(i \in N^+)$ 分解后的最大乘积。

这种情况下乍一看似乎无法转移，因为有后效性，前面的数分解出 $k$ 那么后面就不能分解出 $k$ 了。

既然如此，可以尝试改变状态，多加几维限制。

思考后得出：设 $f(i,j)$ 表示正整数 $i(i \in N^+)$ 分解出的最大整数为 $j$ 时的最大乘积。

初始状态：$\forall i \in [0,n],f(0,i) = 1$

状态转移方程：$f(i,j) = \max\limits_{k=1}^{j - 1} f(i - j,k) \times j$

最终状态 $\max\limits_{i=0}^n f(n,i)$

然而这样是 $O(N^3)$ 的，考虑优化。

令 $s(i,j) = \max\limits_{k=1}^j f(i,k)$

则状态转移方程会变成：$f(i,j) = s(i - j,j - 1) \times j$

初始 $\forall i \in [0,n],s(0,i) = 1$

答案为 $s(n,n)$

这样用 unsigned long long 可以过 $60%$ 的测试数据，但换成高精度则会出现一堆绿色的字母。

（upd:测试时发现，其实根据数学知识，每次转移的 $j$ 并不会太大，有兴趣的可以打个表把 $j$ 的范围缩小些，这样应该能直接 AC）

CODE

法二：

（此方法我暂时给不出严谨的证明，只能感性理解给个大概意思）

再仔细想一想，难道这个 DP 就一定要二维吗？

再想一想，假设我们把 $i$ 分解为 $\{a_1,a_2\ldots a_k \}$，要枚举一个 $a_j(1\le j \le k)$ 进行状态转移。

不难发现，每个数字分别顺序的先后并不影响它对答案的贡献。

换言之，不论枚举的顺序如何，最优状态也一定会被遍历到。

基于此，我们令 $f_i$ 为 $i$ 分解的最优答案，用 bitset 或者 bool 数组记录一下哪些数字被选上了，转移一下就好了。

这个转移方程相当简单，就不写了，详情见 AC 代码。

原式可以化为

$\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)。

给我自己的博客打个广告，关于莫比乌斯反演和整除分块上面有详细的讲解。

首先，我们求简化版问题：求 $\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}$

于是转化为了四个上面的简化版问题。

实际上，简化版问题也有对应的题目，可以直接水掉。

3220. [SDOI 2008] 仪仗队

3609. [BZOJ 1101] Zap

树形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}$$

给我自己的博客打个广告(没有写过几篇文章)

给定非负整数 $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))$

最后，对通解进行一些调整，就得到了最小整数解