首页 > 其他 > 详细

BZOJ.4052.[Cerc2013]Magical GCD(思路)

时间:2019-01-07 11:06:02      阅读:166      评论:0      收藏:0      [点我收藏+]

BZOJ

gcd有结合律,而且gcd每次改变至少会变小两倍,而且只会减小。
所以对于每个右端点,可以暴力维护每种gcd出现的最靠前的位置(只有\(log\)种gcd)。

//1116KB    728MS
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=105;

char IN[MAXIN],*SS=IN,*TT=IN;

inline LL read()
{
    LL now=0; register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}
LL Gcd(LL x,LL y)
{
    return y?Gcd(y,x%y):x;
}

int main()
{
    static int pos[N];
    static LL val[N];

    for(int T=read(); T--; )
    {
        int n=read(); LL ans=0;
        for(int i=1,t=0; i<=n; ++i)
        {
            LL ai=read();
            int las=t; t=0;
            for(int j=1; j<=las; ++j)
            {
                LL tmp=Gcd(val[j],ai);
                if(val[t]!=tmp) val[++t]=tmp, pos[t]=pos[j], ans=std::max(ans,tmp*(i-pos[j]+1));
            }
            if(val[t]!=ai) val[++t]=ai, pos[t]=i, ans=std::max(ans,ai);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

BZOJ.4052.[Cerc2013]Magical GCD(思路)

原文:https://www.cnblogs.com/SovietPower/p/10231927.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!