====== 结论 3 ======

===== 1、等差序列判定 =====

给定一个序列 $a_1,a_2\cdots a_n$，则 $\max(a_i)-\min(a_i)\ge (n-1)\times \text{gcd}(a_2-a_1,a_3-a_2\cdots a_n-a_{n-1})$。

等号成立充要条件为 $a_1,a_2\cdots a_n$ 从小到大排列后可以构成等差序列。

证明：设 $g=\text{gcd}(a_2-a_1,a_3-a_2\cdots a_n-a_{n-1})$。

由于 $g\mid a_{i+1}-a_i,a_{i+2}-a_{i+1}\cdots a_j-a_{j-1}$，所以 $g\mid a_j-a_i$，得 $\text{gcd}(g,a_j-a_i)=g$。

于是 $g=\text{gcd}(a_i-a_j)(1\le i,j\le n)$。将 $a_i$ 从小到大排序得到 $b_1,b_2\cdots b_n$ ，则 

$$
g\le \text{gcd}(b_2-b_1,b_3-b_2\cdots b_n-b_{n-1})\le \min(b_2-b_1,b_3-b_2\cdots b_n-b_{n-1})\le \frac {b_2-b_1+b_3-b_2\cdots +b_n-b_{n-1}}{n-1}=\frac {b_n-b_1}{n-1}
$$

即 $g\le \frac{\max(a_i)-\min(a_i)}{n-1}$。当 $a_i$ 构成等差序列时有 $\frac {\max(a_i)-\min(a_i)}{n-1}\mid g$，此时有 $\frac {\max(a_i)-\min(a_i)}{n-1}=g$。证毕。


===== 2、数值分配 =====

给定序列 $A$，要求构造序列 $B,C$ 使得：

  - $a_i=b_i+c_i$
  - 序列 $B$ 非严格单调递增(即不减)
  - 序列 $B$ 非严格单调递减(即不增)

要求最小化 $\sum |b_i|+|c_i|$。则一定存在最优解满足 $b_{i+1}=b_i+\max(a_{i+1}-a_i,0),c_{i+1}=c_i+\min(a_{i+1}-a_i,0)$。具体见 [[https://atcoder.jp/contests/arc123/editorial/2321|证明]]。

===== 3、因子个数 =====

一个数 $n$ 的因子个数不超过 $O\left(n^{f(n)}\right)$，$f(n)$ 大致递减且 $n$ 比较大时可认为 $f(n)\le \frac 13$，例如 $n\le 10^{18}$ 时因子数至多在 $10^5$ 左右。

===== 4、加法运算 =====

$a+b=a|b+a\And b$