[JSOI2015]最大公约数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long lol;
 7 int n,cnt[100001];
 8 lol Gcd[100001][30];
 9 int lst[100001][30];
10 lol a[100001];
11 lol ans;
12 lol gcd(lol a,lol b)
13 {
14     if (!b) return a;
15     return gcd(b,a%b);
16 }
17 lol max(lol a,lol b)
18 {
19     if (a>b) return a;
20     return b;
21 }
22 int main()
23 {int i,j;
24     cin>>n;
25     for (i=1;i<=n;i++)
26      scanf("%lld",&a[i]);
27     for (i=1;i<=n;i++)
28     {
29         cnt[i]=1;
30         Gcd[i][cnt[i]]=a[i];
31         lst[i][cnt[i]]=i;
32         ans=max(ans,a[i]);
33             for (j=1;j<=cnt[i-1];j++)
34              {
35                  cnt[i]++;
36                  Gcd[i][cnt[i]]=gcd(Gcd[i][cnt[i]-1],Gcd[i-1][j]);
37                  lst[i][cnt[i]]=lst[i-1][j];
38                  ans=max(ans,(lol)(i-lst[i][cnt[i]]+1)*Gcd[i][cnt[i]]);
39                  if (Gcd[i][cnt[i]]==Gcd[i][cnt[i]-1]) 
40                  {
41                      cnt[i]--;
42                      lst[i][cnt[i]]=lst[i-1][j];
43                  }
44              }
45     }
46     cout<<ans;
47 }