从CF1920C看同余的一个性质

https://codeforces.com/problemset/problem/1920/C

同余的一个性质：

证明很显然，但是想不到这个性质

题意

给你 (n) 个数，划分 (k) 段，每段在对 (m(m\ge 2)) 取模之后相等即为一个合法方案，问有多少个合法方案。

断点

//check是能O(n)的
//问题在于怎么check
//经验证,  m = 2, 3, gcd(all(ai))... 时都可能有解
//16 4 | 13 4 (mod 3)
//不是去找几个特解

到此就卡死了

不能去找 (m) 的值，然后代入验证。

解法

[a \equiv b\pmod m \rightarrow
m \mid (a -b)
]

那么问题就转化成了给两个数 (a, b)，问 (a, b) 是否能在模一个数的意义下同余，可能的话求出m。

结果拿这个问题找 AI 一问，AI 给了个 (m | (a - b))，整个问题就解决了。

一个很显然的思路：

对所有段同位置下的数的差值 (a_j - a_i(i\equiv j\pmod k)) 取 (\gcd_{i\pmod k})，然后再对这个 (\gcd) 数组取 (\gcd)，如果答案不为 (1)，就说明找到了一个 (m)。