竟然可以暴力?

题目传送门

大致思路

观察到$(1≤a_i≤10^9)$这一数据范围内的最小公倍数顶多 30 个 $(10^9<2^{30})$
于是我们可以暴力枚举所有区间,顶多枚举 30 次区间,判断是否该区间存在区间的最小公倍数,更新答案
递归实现好操作一点

Code

const int N = 100721;
int ans=0;
vector<int> a(N);

int lcm(int x,int y) {
    return (x*y)/__gcd(x,y);
}

void check(int l,int r) {
    if (l>=r) return;
    int LCM=1;
    for (int i=l; i<=r; i++) LCM = lcm(LCM,a[i]);
    bool valid=true;
    for (int i=l;i<=r;i++) {
        if (a[i]==LCM) {
            valid=false;
            check(l,i-1);
            l=i+1;
        }
    }
    if (valid) ans=max(ans,r-l+1);
    else check(l,r);
}

void solve() {
    ans=0;
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    check(1,n);
    cout << ans<<el;
}