题目

对于一个由正整数组成的序列， Magical GCD 是指一个区间的长度乘以该区间内所有数字的最大公约数。给你一个序列，求出这个序列最大的 Magical GCD。

分析

根据暴力的思想，

\(枚举i，枚举j，a[j]=gcd(a[j],a[i])\)

答案就是\(max(a[j]*(i-j+1))\)

显然，当\(a[j]=a[j-1]\)的时候，\(a[j]\)就一定不会更新ans，所以，弄个双向链表，把\(a[j]\)踢掉。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const int mo=1000000007;

const int N=100005;

using namespace std;

long long a[N],n,m,T,p,q,last[N],next[N],ans;

long long gcd(long long x,long long y)

{

	if(x!=0) return gcd(y%x,x);

	else return y;

}

int main()

{

	scanf("%lld",&T);

	while(T--)

	{

		scanf("%lld",&n);

		next[0]=1;

		for(int i=1;i<=n;i++)

		{

			scanf("%lld",&a[i]);

			last[i]=i-1;

			next[i]=i+1;

		}

		last[1]=next[n]=0;

		ans=0;

		for(int i=1;i<=n;i++)

			for(int j=next[0];j<=i && j;j=next[j])

			{

				a[j]=gcd(a[j],a[i]);

				ans=max(a[j]*(i-j+1),ans);

				if(a[j]==a[last[j]])

				{

					next[last[j]]=next[j];

					last[next[j]]=last[j];

				}

			}

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

	}

}

巴特西

【NOIP2014模拟8.17】Magical GCD

题目

分析

最新文章

热门文章