環上k劃分的和的gcd的最大值【gcd基本性質的利用】

今早看到的題，想了下會做了，但是覺得這題挺有意思的，于是打算寫一下做法。本題利用了gcd的基本性質：更相減損法以及結合律，平時做gcd的題基本沒用到過這兩性質，而本題對這性質進行了充分利用。

思路：

首先我們考慮給一個序列，我們該怎麼做。

令 fn=∑ni=1ai 。

我們考慮序列的一個 k+1 劃分 fx1,fx2−fx1,fx3−fx2,...,fn−fxk ，記為 {x1,x2,x3,...,xk−1,xk} 。

令 A=fx1,B=fx2−fx1,C=fx3−fx2 。

現在我們有 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 劃分 {x1,x2,x3,...,xk−1,xk} 等價于 gcd(fx1,fx2,fx3,...,fxk,fn) 。

因為序列的任意一個劃分總是包含 fn ，是以答案一定是 fn 的約數。

接下來，考慮枚舉 gcd 的值 g （即枚舉答案，fn的約數），即 fn 的約數(不超過 1e4 個)，然後計算 fimodg=0 的個數，假設為 x 個，則說明1~ x 的劃分的答案均可為此值。

了解了鍊上的做法，接下來考慮環上的做法。

考慮環上的斷點為n和 1 之間，記為0，則答案即鍊上求得的答案。

現在考慮将斷點向右移動 x 機關，即fx屬于最後一個區間，且 1 ~x之間不可能再有斷點，否則我們在之前便已枚舉過。

然後枚舉 gcd 的值 g ，然後計算x+1~ n 内滿足fymodg=fxmodg的 y 的個數。

為了加速這一過程，考慮先枚舉gcd的值 g ，再枚舉斷點x，然後看斷點之後滿足 fymodg=fxmodg 的 y 的個數。

其實無需真的枚舉斷點，換個角度思考，枚舉斷點等價于枚舉fxmodg的值，而每個 fxmodg 的值隻有編号最小的有用，因為在這樣的 x 之後的y才會盡可能多。

既然知道是什麼原理了，最後總結一下做法：

1.枚舉 gcd 的值 g ，

2.令bi=fimodg，

3.對 b數組 排序，然後統計相同的值出現的次數，

4.初始化 ans[] ，令值全為1，

5.假設值為 x 的出現了y次，則令 ans[y]=max(ans[y],x) ，

6.對 ans 更新得字尾最大值。

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

7.第 i 行輸出ansi。