A simple Blog for wyx I've been down the bottle hoping.
4488: [Jsoi2015]最大公约数 && 4052: [Cerc2013]Magical GCD
发表于: | 分类: Oi | 评论:0 | 阅读:148

当我发现Js出了一道原题的时候我也是……顺便说一下,其实4052也不是原题,原题是一道cf题2333333 现在估计也是把出题人憋坏了


首先你需要明确一个事情,对于一段区间$[L,R]$,他的$gcd$一定是不小于$[L,R+1]$的

进一步我们可以发现,就算是每次去掉一个最小的质因数,假设他是2,那么也最多有$\log$个不同的$gcd$

说白了就是固定左端点之后,区间的$gcd$最多变化$log$次

所以我们每次二分下一个位置就行辣

复杂度$O(n\log^2n)$,据说有一个$log$的单调栈做法?

【我还真的被卡了一下,开始用的线段树直接作死了

#include <cmath>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100000+5;

inline LL read() {
    LL x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

LL F[N][18], a[N];

inline LL calc(int x,int y) {
    int len = y - x + 1, tt = (int)log2(len);
    return __gcd(F[x][tt],F[y-(1<<tt)+1][tt]);
}

int main() {//freopen("tt.in","r",stdin);
    int T = 1;
    while(T-- ){
        int n = read();
        for(int i=1;i<=n;++i) a[i] = read();
        for(int i=1;i<=n;++i) F[i][0] = a[i];
        for(int i=n;i;--i) for(int j=1;j<=17;++j) 
            if(i+(1<<j)-1<=n) F[i][j] = __gcd(F[i][j-1],F[i+(1<<(j-1))][j-1]);
        LL ans = 0;
        for(int i=1;i<=n;++i) {
            int last = i-1, l, r;
            LL lastg = a[i];
            while(last != n) {
                l = last + 1, r = n + 1;
                while(l<r) {
                    int mid = (l+r) >> 1;
                    if(calc(i,mid) == lastg) l = mid + 1;
                    else r = mid;
                }
                l --;
                ans = max(ans,lastg*(l-i+1));
                last = l; lastg = __gcd(lastg,a[l+1]);
            }
        }
        printf("%lld\n", ans);
    }
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP