【 8.4 】 source code - [math] [calendar] [delete library 】 【 is not a simple sequence (Bonus) 】

#47. 数学

题意：给定整数 $n$ ,Fat professor wants to $1\sim n$ 这 $n$ 个数字分成两组,Each group has at least one number,And make the greatest common divisor of the sum of the two sets of numbers the largest,Please output the largest greatest common divisor.

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

思路：首先 $1\sim \frac{n\times (n+1)}{2}$ Any number of can be represented by these numbers,Then the problem translates to having two positive integers satisfy $a+b=m=\frac{n\times (n+1)}{2}$ ,最大化 $\gcd (a,b)$

Let's push the formula from the definition of tossing and dividing $\gcd (a,b)=\gcd (a,m-a)=\gcd (a,m)$ ,$a$ 的取值为 $a\in [1,m-1]$ ,Then the problem turns into finding $m$ 的最大因子,Radical enumeration to find the smallest prime factor.

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))$ into several congruent systems,Every congruence has it $C_{cnt}^2$ 个贡献.计算一下即可.

总结了一下：

有连续的 $n$ 个整数,Then these integers are modulo $p$ 意义下,According to the size of the congruence system, it is divided into two types：

• 有 $n\%p$ group congruence,大小为 $\lceil \frac{n}{p}\rceil$
• 有 $p-n\%p$ group congruence,大小为 $\lfloor \frac{n}{p}\rfloor$

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

#855. 删库

题意：

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

思路：字典树上 dfs + 贪心.At the beginning, I forgot about the dictionary tree.

First we build the dictionary tree.We select a string and delete the corresponding string from the set,Equivalent to cutting a subtree from the dictionary tree,Marker points on the subtree $\le k$ .

那么贪心思路就是：我们 dfs After finishing the son of a node,Count how many markers there are in the subtree.如果标记点 $\le k$ ,Then our greedy strategy is to backtrack directly,Do not delete at this node,Because we can combine with markers on other sibling subtrees after backtracking,deleted together,minimize the number of deletions;反之,We must delete some child subtrees at this point.We sequentially delete the subtree with the largest number of markers,Makes backtracking with fewer markers.

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

#883. Uncomplicated numbers（Bonus）

题意：给定长度为 $n(1\le n\le 10^6)$ 的序列 $a(0\le a\le 10^6)$ ,Each operation can decrement a number by one,Add one to the number adjacent to this number.Ask the least number of operands to make the sequence $\gcd (a)\ge 2$ .

题解：(枚举/贪心) 代码源每日一题 Div1 Uncomplicated numbers（Bonus）

思路：First there is a theorem：序列的 $\gcd$ Equal to serial difference $\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$ is equal to the sequence prefix sum $\gcd$ .

Our operations on adjacent numbers of the sequence are equivalent to single-point addition or subtraction of the prefix and the sequence.我们枚举 $sum$ 的因子 $x$ ,The question turns into how many times to operate so that each prefix is $x$ 的倍数, ${\sum }_{i=1}^{n-1}\min (a_i\%p,p-a_i\%p)$ .

The problem solution is analogized from a classic problem.

给定两个序列 $a,b$ ,It is also similar to the addition and subtraction of adjacent numbers,问对 $a$ At least how many times the operation makes and $b$ 完全相等.

定义 $ste{p}_i$ 表示为前 $i$ The minimum number of operations to be exactly equal,那么 $ste{p}_i=ste{p}_{i-1}+|s{a}_i-s{b}_i|$ .可以理解为,当前面 $i$ After the number operation is completed,会从 $a_i$ Take this number here or send some numbers,We in order to make $a_i=b_i$ ,Need to bring some numbers or send some numbers away $a_{i+1}$ ,The number of operations is $|s{a}_i-s{b}_i|$

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