环上k划分的和的gcd的最大值【gcd基本性质的利用】

本文主要是介绍环上k划分的和的gcd的最大值【gcd基本性质的利用】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今早看到的题，想了下会做了，但是觉得这题挺有意思的，于是打算写一下做法。本题利用了gcd的基本性质：更相减损法以及结合律，平时做gcd的题基本没用到过这两性质，而本题对这性质进行了充分利用。

思路：
首先我们考虑给一个序列，我们该怎么做。
令$f_n=\sum_{i=1}^n a_i$。
我们考虑序列的一个$k+1$划分$f_{x_1},f_{x_2}-f_{x_1},f_{x_3}-f_{x_2},...,f_n-f_{x_k}$，记为$\{x_1,x_2,x_3,...,x_{k-1},x_k\}$。
令$A=f_{x_1},B=f_{x_2}-f{x_1},C=f{x_3}-f_{x_2}$。
现在我们有$gcd$的两条基本但十分重要的性质：
1.$gcd$本质是更相减损法，即$gcd(A,B-A)=gcd(A,B)$。
2.$gcd$满足结合律，即$gcd(gcd(A,B),C)=gcd(A,gcd(B,C))$。

  gcd(A,B-A,C-B)=gcd(gcd(A,B-A),C-B)=gcd(gcd(A,B),C-B)=gcd(A,gcd(B,C-B))=gcd(A,gcd(B,C))=gcd(A,B,C)

根据数学归纳法，可以得出结论：序列上的任意一个$k+1$划分$\{x_1,x_2,x_3,...,x_{k-1},x_k\}$等价于$gcd(f_{x_1},f_{x_2},f_{x_3},...,f_{x_k},f_n)$。
因为序列的任意一个划分总是包含$f_n$，因此答案一定是$f_n$的约数。
接下来，考虑枚举$gcd$的值$g$（即枚举答案，$f_n$的约数），即$f_n$的约数(不超过$1e4$个)，然后计算$f_i\bmod g=0$的个数，假设为$x$个，则说明$1$~$x$的划分的答案均可为此值。

了解了链上的做法，接下来考虑环上的做法。
考虑环上的断点为$n$和$1$之间，记为$0$，则答案即链上求得的答案。
现在考虑将断点向右移动$x$单位，即$f_x$属于最后一个区间，且$1$~$x$之间不可能再有断点，否则我们在之前便已枚举过。
然后枚举$gcd$的值$g$，然后计算$x+1$~$n$内满足$f_y\bmod g=f_x\bmod g$的$y$的个数。
为了加速这一过程，考虑先枚举$gcd$的值$g$，再枚举断点$x$，然后看断点之后满足$f_y\bmod g=f_x\bmod g$的$y$的个数。
其实无需真的枚举断点，换个角度思考，枚举断点等价于枚举$f_x\bmod g$的值，而每个$f_x\bmod g$的值只有编号最小的有用，因为在这样的$x$之后的$y$才会尽可能多。

既然知道是什么原理了，最后总结一下做法：
1.枚举$gcd$的值$g$，
2.令$b_i=f_i\bmod g$，
3.对$b数组$排序，然后统计相同的值出现的次数，
4.初始化$ans[]$，令值全为1，
5.假设值为$x$的出现了$y$次，则令$ans[y]=max(ans[y],x)$，
6.对$ans$更新得后缀最大值。

for ( int i = n ; i >= 1 ; --i ) {ans[i-1] = max ( ans[i - 1] , ans[i] ) ;
}

7.第$i$行输出$ans_i$。

这篇关于环上k划分的和的gcd的最大值【gcd基本性质的利用】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---