bzoj 4488: [Jsoi2015]最大公约数-白红宇

bzoj 4488: [Jsoi2015]最大公约数

阅读量：4336 次

发布时间：2019-06-07

本文共 1203 字，大约阅读时间需要 4 分钟。

4488: [Jsoi2015]最大公约数

Time Limit: 10 Sec Memory Limit: 256 MB

Submit: 270 Solved: 154

[][][]

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

30 60 20 20 20

Sample Output

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

HINT

Source

[][][]

题解：若n个元素，其后缀所有不同的gcd，不会超过log(n)个，因此可以枚举右端点，进行暴力更新,我们可以设st[2][NMAX],in[2][NMAX]数组，

st数组存取后缀gcd，in数组存取第一次出现gcd的位置,st和in中的2表示有两个状态（即以上一个点为后缀和当前点为后缀）,每次都用上一个点

的信息更新当前点的信息。

c++ code:

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          using namespace std;const int NMAX=1e5+7;typedef long long ll;ll st[2][NMAX],in[2][NMAX],p,top[2],a[NMAX];map
          
           my;ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}void init(){ top[0]=top[1]=p=0;}int main(){ int n; init(); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); st[p][top[p]]=a[1]; in[p][top[p]++]=1; ll ans=a[1]; for(int i=2;i<=n;i++) { my.clear(); for(int j=0;j

转载于:https://www.cnblogs.com/lemon-jade/p/8604214.html

你可能感兴趣的文章