题目

小A有一个环，环上有n个正整数。他有特殊的能力，能将环切成k段，每段包含一个或者多个数字。对于一个切分方案，小A将以如下方式计算优美程度：

首先对于每一段，求出他们的数字和。然后对于每段的和，求出他们的最大公约数，即为优美程度。

他想通过合理地使用他的特殊能力，使得切分方案的优美程度最大。

分析

首先知道，每个可能的优美程度一定是\(\sum a_i(=m)\)的约数，

因为m的约数最多只有4000多个，

所以，我们枚举m的约数i，

将a所有数mod i

发现假设某个余数为j(i>j)，

分布最这些地方：

那么每两个余数为j夹着的区间（因为这是环，所以头尾合在一起也当做一个区间）一定能被i整除，

也就是说，这个环最多可以被分成j的个数个段，以及i这个优美程度可以最多可以将环分成i段。

这个处理j的个数可以用快排，如何想快点可以用hash。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           const int maxlongint=2147483647;const int N=4005;using namespace std;long long a[N],n,mx[N],t[N*N],m,b[N];int main(){ scanf("%lld",&n); for(long long i=1;i<=n;i++) scanf("%lld",&a[i]),m+=a[i]; for(int i=1;i<=n;i++) a[i]+=a[i-1]; mx[1]=m; b[0]=-1; b[n+1]=-1; for(long long i=1;i<=sqrt(m);i++) if(m%i==0) { long long mo=i; for(int i1=1;i1<=n;i1++) b[i1]=a[i1]-a[i1]/mo*mo; sort(b+1,b+1+n); int sum=0,mx1=1; for(int i1=1;i1<=n+1;i1++) { if(b[i1]!=b[i1-1]) { mx1=max(mx1,sum); sum=1; } else sum++; } mx[mx1]=max(mx[mx1],mo); mo=m/i; for(int i1=1;i1<=n+1;i1++) b[i1]=a[i1]-a[i1]/mo*mo; sort(b+1,b+1+n); sum=0; mx1=1; for(int i1=1;i1<=n;i1++) { if(b[i1]!=b[i1-1]) { mx1=max(mx1,sum); sum=1; } else sum++; } mx[mx1]=max(mx[mx1],mo); } for(int i=n;i>=1;i--) mx[i]=max(mx[i],mx[i+1]); for(int i=1;i<=n;i++) printf("%lld\n",mx[i]);}