hiho1246（数学求模）

input

1<=n<=2000

a1 a2 ... an 1<=ai<=5*10e7

output

n行，第i行指切成i段，每段和的最大公约数的最大值

做法：环形数组切成n段，每段和的最大公约数肯定是总数的约数，然后只要求出每个约数对应的最大段数即可，即前缀和模d出现最多的次数

 #include <cstdio>

 #include <queue>

 #include <cstring>

 #include <iostream>

 #include <cstdlib>

 #include <algorithm>

 #include <vector>

 #include <map>

 #include <set>

 #include <ctime>

 #include <cmath>

 using namespace std;

 long long d[],a[];

 int n,dn,k[];

 void fac(long long x)

 {

     int m=sqrt(x)+0.5;

     dn=;

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

         if(x%i==) d[dn++]=i;

     for(int i=dn-;i>=;i--)

         d[dn++]=x/d[i];

 }

 /*//错的,不能保证最大

 int findk(int idx)找到第一个出现重复的r，即出现了(r+nd)%d=r

 {

     long long r;

     int i,k;

     set<long long> q;

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

     {

         r=a[i]%d[idx];

         if(!q.count(r)) q.insert(r);

         else break;

     }

     i<n&&q.count(a[i]%d[idx])?k=2:k=1;

     i++;

     for(;i<n;i++)

         if(a[i]%d[idx]==r) k++;

     return k;

 }

 */

 const int HASH=;

 int head[HASH],next[HASH],num[HASH];

 long long st[HASH];

 int insert(int s)

 {

     int h=st[s]%HASH;

     int u=head[h];

     while(u)

     {

         if(st[u]==st[s])

         {

             num[u]++;

             return ;

         }

         u=next[u];

     }

     next[s]=head[h];

     head[h]=s;

     return ;

 }

 int findk(int idx)//出现最多次的r的次数为该环切成最多段数能被d整除

 {

     memset(head,,sizeof(head));

     int i,j,maxk=-;

     for(i=,j=;i<n;i++)

     {

         st[j]=a[i]%d[idx];

         //printf("st1 %lld\n",st[j]);

         num[j]=;

         if(insert(j)) j++;

     }

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

         if(num[i]>maxk) maxk=num[i];

     return maxk;

 }

 int main()

 {

     freopen("/home/user/桌面/in","r",stdin);

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

     {

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

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

         {

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

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

         }

         fac(a[n-]);

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

             k[i]=findk(i);

         //for(int i=0;i<dn;i++) printf("the%d %lld %d\n",i+1,d[i],k[i]);

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

             for(int j=dn-;j>=;j--)

                 if(k[j]>=i)

                 {

                     printf("%lld\n",d[j]);

                     break;

                 }

     }

     //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);

     return ;

 }