hiho1246（数学求模）

input

1<=n<=2000

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

output

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

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

  1 #include <cstdio>
  2 #include <queue>
  3 #include <cstring>
  4 #include <iostream>
  5 #include <cstdlib>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <map>
  9 #include <set>
 10 #include <ctime>
 11 #include <cmath>
 12 
 13 using namespace std;
 14 
 15 long long d[1200],a[2010];
 16 int n,dn,k[1200];
 17 
 18 void fac(long long x)
 19 {
 20     int m=sqrt(x)+0.5;
 21     dn=0;
 22     for(int i=1;i<=m;i++)
 23         if(x%i==0) d[dn++]=i;
 24     for(int i=dn-1;i>=0;i--)
 25         d[dn++]=x/d[i];
 26 }
 27 
 28 /*//错的,不能保证最大
 29 int findk(int idx)找到第一个出现重复的r，即出现了(r+nd)%d=r
 30 {
 31     long long r;
 32     int i,k;
 33     set<long long> q;
 34     for(i=0;i<n;i++)
 35     {
 36         r=a[i]%d[idx];
 37         if(!q.count(r)) q.insert(r);
 38         else break;
 39     }
 40     i<n&&q.count(a[i]%d[idx])?k=2:k=1;
 41     i++;
 42     for(;i<n;i++)
 43         if(a[i]%d[idx]==r) k++;
 44     return k;
 45 }
 46 */
 47 
 48 
 49 const int HASH=2007;
 50 int head[HASH],next[HASH],num[HASH];
 51 long long st[HASH];
 52 
 53 int insert(int s)
 54 {
 55     int h=st[s]%HASH;
 56     int u=head[h];
 57     while(u)
 58     {
 59         if(st[u]==st[s])
 60         {
 61             num[u]++;
 62             return 0;
 63         }
 64         u=next[u];
 65     }
 66     next[s]=head[h];
 67     head[h]=s;
 68     return 1;
 69 }
 70 
 71 int findk(int idx)//出现最多次的r的次数为该环切成最多段数能被d整除
 72 {
 73     memset(head,0,sizeof(head));
 74     int i,j,maxk=-1;
 75     for(i=0,j=1;i<n;i++)
 76     {
 77         st[j]=a[i]%d[idx];
 78         //printf("st1 %lld
",st[j]);
 79         num[j]=1;
 80         if(insert(j)) j++;
 81     }
 82     for(int i=1;i<j;i++)
 83         if(num[i]>maxk) maxk=num[i];
 84     return maxk;
 85 }
 86 
 87 int main()
 88 {
 89     freopen("/home/user/桌面/in","r",stdin);
 90     while(scanf("%d",&n)==1)
 91     {
 92         scanf("%lld",&a[0]);
 93         for(int i=1;i<n;i++)
 94         {
 95             scanf("%lld",&a[i]);
 96             a[i]+=a[i-1];
 97         }
 98         fac(a[n-1]);
 99         for(int i=0;i<dn;i++)
100             k[i]=findk(i);
101         //for(int i=0;i<dn;i++) printf("the%d %lld %d
",i+1,d[i],k[i]);
102         for(int i=1;i<=n;i++)
103             for(int j=dn-1;j>=0;j--)
104                 if(k[j]>=i)
105                 {
106                     printf("%lld
",d[j]);
107                     break;
108                 }
109     }
110     //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
111     return 0;
112 }

View Code