hihoCoder #1246 : 王胖浩与环 （数学）

题意：

　　有一个环形序列，可以将其切成连续的k段子序列，那么gcd( 每段子序列的和 )就是优美程度。输出n个整数，表示当k=[1, n] 时的最大优美程度。

思路：

　　观察一下，当切成1段的时候，gcd就是sum[整个序列]，为最大。考虑切成2段，那么最好就是能让这个环切成2段和为sum[整个序列]/2的子序列了。考虑切成3段，那么最好就是能让这个环切成3段和为sum[整个序列]/3的子序列了。继续下去，这不就是求sum[整个序列]的约数吗？

　　假设约数有k个，从大到小分别为factor[1～R]。那么其中有些因数是可能组不成的，得去掉那些组不成的。假设sum[整个序列]最多能切成cnt段和为factor[t]的连续子序列，那么段数i<=cnt的，答案都是factor[t]了，取最大即可。

　　问题在于如何求出切成长为factor[t]的最多段数cnt[t]？当前缀和pre%factor=r出現了m次時应该是这样的： ..|xxxx|xxxx|......|xxx|xxxx|.. （共有m个切口|），观察到除了首尾之外，其他每段都是d的倍数，且首尾之和也是d的倍数（因为sum[整个序列]=k*d）。那么对于factor[t]，只需要枚举r来求出最大的m即可。

 #include<bits/stdc++.h>

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const int N=;

 vector<LL> factor, cnt;

 LL a[N];

 map<LL,LL> mapp;

 int main()

 {

     freopen("input.txt","r",stdin);

     int n;

     while(~scanf("%d",&n))

     {

         for(int i=; i<=n; i++)

         {

             scanf("%lld",&a[i]);

             a[i]+=a[i-];

         }

         for(LL i=; i*i<=a[n]; i++)

         {

             if(a[n]%i==)

             {

                 factor.push_back(a[n]/i);

                 factor.push_back(i);//多一个也不影响结果

             }

         }

         sort(factor.begin(),factor.end());

         deque<LL> ans;

         for(int k=factor.size()-,i=; k>=; k--)

         {

             LL big=, c=factor[k];

             mapp.clear();

             for(int j=; j<=n; j++)

                 big=max(big,++mapp[a[j]%c]);

             while(i<=n&&big>=i)

             {

                 ans.push_back(c);

                 i++;

             }

         }

         while(!ans.empty())

         {

             printf("%lld\n",ans.front());

             ans.pop_front();

         }

     }

     return ;

 }

AC代码