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个，所以可以直接暴力，判断包涵当前这个点的公约数，然后统计所有的答案，同样的公约数当然位置越前面越好。

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<map>
 7 
 8 #define zz map<ll,ll>::iterator
 9 #define ll long long
10 #define N 100007
11 #define ll long long
12 using namespace std;
13 inline ll read()
14 {
15     ll x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
17     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 
21 int n;
22 ll a[N],ans;
23 map<ll,ll>p1,p2;
24 
25 ll gcd(ll a,ll b)
26 {
27     return b?gcd(b,a%b):a;
28 }
29 int main()
30 {
31     n=read();
32     for (int i=1;i<=n;i++)
33     {
34         a[i]=read(),ans=max(ans,a[i]);
35         for (zz it=p1.begin();it!=p1.end();it++)
36         {
37             ll g=gcd((*it).first,a[i]);
38             ans=max(ans,g*((ll)i-(*it).second+1ll));
39             if (!p2.count(g)) p2[g]=(*it).second;
40             else p2[g]=min(p2[g],(*it).second);
41         }
42         if (!p2.count(a[i])) p2[a[i]]=i;
43         p1=p2;
44         p2.clear();
45     }
46     printf("%lld
",ans);
47 }

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