因數，前綴和

題意：
給你一個循環數組，你要將它截成k段，然后每段有一個區間和，所有的區間和求gcd，就是優美程度，你要使得優美程度最大。k不是輸入的，而是你要輸出截1段，2段...n段的最優值

數據范圍：
n<=2000，ai<=5*10^7

思路：

我算了一下，暴力dp要O(n4)...

注意到，這個優美程度肯定是數組所有元素的和的因子(這個不難證明)，那么我們可以把問題反轉過來考慮，考慮要截出優美程度為因子x，最多能截多少段。

這里有個很好的性質就是，因子x能截y段，那么就肯定能截y-1段，y-2段...因為你可以把其中相鄰的兩段合起來，這樣它們的區間和還是會整除x的

從頭到尾地掃，維護sum，當sum能整除x就截。由于是循環數組，這樣的話就要枚舉開頭去截得到的所有答案求個max。這樣的話復雜度就是O(n2*d)，d是sum的因子數量。由于sum是longlong范圍的，因此會出現有些數因子十分多，d就不是常數或者logn這么簡單了

我們要優化掉枚舉開頭這個東西，有一個很重要的結論，區間和整除，就是前綴和同余！因此我們只需要求出前綴和，然后把它們分組，按模因子x的余數分組。然后最大的那個組的size就是因子x的最多能截的段數。

注意到余數可能是很大的，因此不能直接開個數組記錄，要哈希一下，或者直接用個map。由于前綴和最多才2k個，因此加個log也沒所謂。

我們把每個因子得到的答案都保存下來，輸出截k段的時候，我們直接遍歷所有因子，然后找截的最大段數>=k的并且值最大的因子輸出。最后復雜度是O(nlogn*d)

注意一點，因子越小不意味著能截更多的段數，所以最后那步是遍歷所有因子而不是二分什么的

總結：答案肯定是數組和的因子，把問題反轉，求每個因子最多能截多少段

總結

以上是生活随笔為你收集整理的hiho 挑战赛16 B 王胖浩与环的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。