题解 | #序列操作#

显然操作 $[1,n][1,n]$ 是最优的。

相当于在 $\mathrm{m}\mathrm{o}\mathrm{d}p\backslash mod\; p$ 意义下，令 $a[i]:=a[i]+kxa[i]\; :=\; a[i]\; +\; kx$ 使得 $a[i]=b[i]a[i]\; =\; b[i]$，选定 $xx$ 使得最大的 $kk$ 在所有可能的 $xx$ 中最小。

求该 $xx$.

$a[i]+kx\equiv b[i](\mathrm{m}\mathrm{o}\mathrm{d}p)a[i]\; +\; kx\; \backslash equiv\; b[i]\; \backslash pmod\; p$，可以写成 $kx\equiv b[i]-a[i](\mathrm{m}\mathrm{o}\mathrm{d}p)kx\; \backslash equiv\; b[i]\; -\; a[i]\; \backslash pmod\; p$，那么我们记录所有出现过的 $b[i]-a[i]b[i]\; -\; a[i]$ 值。

枚举 $xx$，对每一个 $xx$，在值域上枚举 $b[i]-a[i]b[i]\; -\; a[i]$，解出对应的 $k_{i}k\_i$，取 $\max k_i\backslash max\; k\_i$ 即为当前 $xx$ 的操作次数。

解 $kx\equiv b[i]-a[i](\mathrm{m}\mathrm{o}\mathrm{d}p)kx\; \backslash equiv\; b[i]\; -\; a[i]\; \backslash pmod\; p$ 我一开始想的是直接 exgcd，不过 $p^2\log pp^2\; \backslash log\; p$ 会超时，卡卡常没卡过去。

预处理出逆元 $x^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}p)x^\{-1\}\; \backslash pmod\; p$，那么 $k\equiv (b[i]-a[i])x^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}p)k\; \backslash equiv\; (b[i]\; -\; a[i])x^\{-1\}\; \backslash pmod\; p$，那么复杂度就降低到 $O(p^2)O(p^2)$ 了。

似乎有一种奇怪的边界情况，$a[i]\mathrm{m}\mathrm{o}\mathrm{d}pa[i]\; \backslash mod\; p$ 后直接相等，此时的操作次数是 $11$ 次，$x=0x=0$ 最优。如果不管的话按上述算法算出来的操作次数是 $00$，不过也没啥区别。