bzoj 4488 [Jsoi2015]最大公约数 结论+暴力

[Jsoi2015]最大公约数

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 302  Solved: 169
[Submit][Status][Discuss]

Description

给定一个长度为 N 的正整数序列Ai对于其任意一个连续的子序列
{A_l,A_l+1...A_r}，我们定义其权值W(L,R )为其长度与序列中所有元素的最大公约数的乘积，即W(L,R) = (R-L+1) ∗ gcd (A_l..A_r)。 
JYY 希望找出权值最大的子序列。

Input

输入一行包含一个正整数 N。
接下来一行，包含 N个正整数，表示序列Ai
1 < =  Ai < =  10^12, 1 < =  N < =  100,000

Output

输出文件包含一行一个正整数，表示权值最大的子序列的权值。

Sample Input

5
30 60 20 20 20

Sample Output

80
//最佳子序列为最后 4 个元素组成的子序列。

HINT

Source

题解：有一个结论，一个序列的gcd最多只有log个，

因为最多只有log个，所以可以直接暴力，判断包涵当前这个点的公约数，然后统计所有的答案，同样的公约数当然位置越前面越好。

 #include<cstring>
 #include<cstdio>
 #include<algorithm>
 #include<iostream>
 #include<cmath>
 #include<map>

 #define zz map<ll,ll>::iterator
 #define ll long long
 #define N 100007
 #define ll long long
 using namespace std;
 inline ll read()
 {
     ll x=,f=;char ch=getchar();
     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
     return x*f;
 }

 int n;
 ll a[N],ans;
 map<ll,ll>p1,p2;

 ll gcd(ll a,ll b)
 {
     return b?gcd(b,a%b):a;
 }
 int main()
 {
     n=read();
     for (int i=;i<=n;i++)
     {
         a[i]=read(),ans=max(ans,a[i]);
         for (zz it=p1.begin();it!=p1.end();it++)
         {
             ll g=gcd((*it).first,a[i]);
             ans=max(ans,g*((ll)i-(*it).second+1ll));
             if (!p2.count(g)) p2[g]=(*it).second;
             else p2[g]=min(p2[g],(*it).second);
         }
         if (!p2.count(a[i])) p2[a[i]]=i;
         p1=p2;
         p2.clear();
     }
     printf("%lld\n",ans);
 }