【8.4】代码源 - 【数学】【历法】【删库】【不朴素的数列（Bonus）】

#47. 数学

题意：给定整数 $n$ ，胖教授想将 $1\sim n$ 这 $n$ 个数字分成两组，每一组至少有一个数，并且使得两组数字的和的最大公约数最大，请输出最大的最大公约数。

题解：(数学/枚举) 代码源每日一题 Div2 数学

思路：首先 $1\sim \frac{n\times (n+1)}{2}$ 的任意一个数都能被这些数表示，那么问题转化为有两个正整数满足 $a+b=m=\frac{n\times (n+1)}{2}$ ，最大化 $\gcd (a,b)$

我们由辗转相除法的定义推一下式子 $\gcd (a,b)=\gcd (a,m-a)=\gcd (a,m)$ ，$a$ 的取值为 $a\in [1,m-1]$ ，那么问题转化为找到 $m$ 的最大因子，根号枚举找一下最小质因子即可。

AC代码：http://oj.daimayuan.top/submission/317961

---

#913. 历法

题意：
题解：(数学) 代码源每日一题 Div1 历法

思路：和 这道题 挺像的。抽象一下：找到一对 $x,y$ 满足 $0\le x,y<min(m,d)$ 且 $x\times d+y=y\times d+x(\mathrm{mod}w)$ 。化简一下， $(y-x)\times (d-1)=0(\mathrm{mod}w)$ ，即 $w|(y-x)\times (d-1)$ ，把 $d-1$ 移到左边 $\frac{w}{\gcd (w,d-1)}|y-x$ ，即 $y=x(\mathrm{mod}\frac{w}{\gcd (w,d-1)})$ 。我们把 $[0,min(m,d))$ 分为若干个同余系，每个同余系都有 $C_{cnt}^2$ 个贡献。计算一下即可。

总结了一下：

有连续的 $n$ 个整数，那么这些整数在模 $p$ 意义下，按照同余系的大小分为两种：

• 有 $n\%p$ 组同余系，大小为 $\lceil \frac{n}{p}\rceil$
• 有 $p-n\%p$ 组同余系，大小为 $\lfloor \frac{n}{p}\rfloor$

AC代码：http://oj.daimayuan.top/submission/318549

---

#855. 删库

题意：

题解：(贪心/字典树) 代码源每日一题 Div1 删库

思路：字典树上 dfs + 贪心。开始的时候忘了还有字典树这东西了。

首先我们构建字典树。我们选择一个字符串并删去集合中对应的字符串，等价于在字典树上割去某子树，子树上的标记点 $\le k$ 。

那么贪心思路就是：我们 dfs 完某个节点的儿子后，统计一下该子树上还有多少个标记点。如果标记点 $\le k$ ，那我们的贪心策略就是直接回溯，不在此节点删除，因为我们回溯后可以和其他兄弟子树上的标记点结合，一起被删去，使得删除次数最小化；反之，我们必须要在此点删除某些儿子子树。我们依次删掉标记点个数最多的子树，使得回溯的标记点更少。

AC代码：http://oj.daimayuan.top/submission/318499

---

#883. 不朴素的数列（Bonus）

题意：给定长度为 $n(1\le n\le 10^6)$ 的序列 $a(0\le a\le 10^6)$ ，每次操作可以把一个数减一，与这个数相邻的数加一。问最少操作数使得序列 $\gcd (a)\ge 2$ 。

题解：(枚举/贪心) 代码源每日一题 Div1 不朴素的数列（Bonus）

思路：首先有一个定理：序列的 $\gcd$ 等于序列差分的 $\gcd$ ，即 $\gcd (a_1,a_2,\cdots ,a_{n-1},a_n)=\gcd (a_1,a_2-a_1,\cdots ,a_i-a_{i-1},\cdots ,a_n-a_{n-1})$ 。同理，序列的 $\gcd$ 等于序列前缀和的 $\gcd$ 。

我们对序列的相邻数的操作等价于对前缀和序列单点加或减。我们枚举 $sum$ 的因子 $x$ ，问题转化为操作多少次使得每个前缀都是 $x$ 的倍数， ${\sum }_{i=1}^{n-1}\min (a_i\%p,p-a_i\%p)$ 。

题解则从一个经典问题类比过来。

给定两个序列 $a,b$ ，也是类似的相邻数加减操作，问对 $a$ 至少操作多少次使得与 $b$ 完全相等。

定义 $ste{p}_i$ 表示为前 $i$ 个数操作为完全相等的最少次数，那么 $ste{p}_i=ste{p}_{i-1}+|s{a}_i-s{b}_i|$ 。可以理解为，当前面 $i$ 个数操作完之后，会从 $a_i$ 这个数这里拿走或者送来若干数，我们为了使得 $a_i=b_i$ ，需要把一些数拿来或者送走若干个数给 $a_{i+1}$ ，操作次数就是 $|s{a}_i-s{b}_i|$

AC代码：http://oj.daimayuan.top/submission/319729