Warning: session_start(): open(/tmp/sess_dfcc1c1bd7df9ffe3057cde9eb9f3e90, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:legal_string:jxm2001:other:结论_3 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:other:结论_3

结论 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$。证毕。

2020-2021/teams/legal_string/jxm2001/other/结论_3.1626831359.txt.gz · 最后更改: 2021/07/21 09:35 由 jxm2001