BZOJ4488: [Jsoi2015]最大公约数

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 个元素组成的子序列。

固定端点的序列一共只有O(logn)种不同的gcd，所以我们枚举右端点，维护不同gcd的左端点集合，右端点改变时重新扫一遍合并一下相同的gcd区间即可。

时间复杂度为O(Nlog^2N)。

#include<cstdio>

#include<cctype>

#include<queue>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i;i=next[i])

using namespace std;

const int BufferSize=1<<16;

char buffer[BufferSize],*head,*tail;

inline char Getchar() {

	if(head==tail) {

		int l=fread(buffer,1,BufferSize,stdin);

		tail=(head=buffer)+l;

	}

	return *head++;

}

typedef long long ll;

inline ll read() {

    ll x=0,f=1;char c=Getchar();

    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=Getchar()) x=x*10+c-'0';

    return x*f;

}

const int maxn=100010;

ll A[maxn],B[maxn],ans;

ll gcd(ll a,ll b) {return !b?a:gcd(b,a%b);}

int n,S[maxn];

int main() {

	n=read();int top=0;

	rep(i,1,n) A[i]=read();

	rep(i,1,n) {

		S[++top]=i;B[top]=A[i];

		dwn(j,top-1,1) {

			B[j]=gcd(B[j],B[j+1]);

			if(B[j]==B[j+1]) {

				rep(k,j+1,top-1) S[k]=S[k+1],B[k]=B[k+1];

				top--;

			}

		}

		rep(j,1,top) ans=max(ans,B[j]*(i-S[j]+1));

	}

	printf("%lld\n",ans);

	return 0;

}

秒客网