UPC-魔法序列（結論+枚舉）

魔法序列

時間限制: 1 Sec 記憶體限制: 128 MB

[送出] [狀态]

題目描述

小E為了完成公主的任務，需排布魔法陣，從中獲得法力。

簡單起見，魔法陣可以看成一個長度為n的序列。序列從左到右都擺放了一張符卡，符卡有一個強度ai。法術的釋放要每個元素互相配合，取得共鳴效果。一個由一些符卡組成的咒語的魔力值為這個咒語中所有符卡的強度的最大公因數乘以符卡的個數。

小E會從魔法陣中選擇一段連續符卡區間[l,r]（包括l，r端點），作為吟唱的咒語。她想知道，咒語最大的魔力值是多少。

輸入

第一行一個整數n，表示符卡個數。

第二行n個正整數，第i個數表示符卡的強度ai。

輸出

輸出一個整數，表示最大的魔力值。

樣例輸入 Copy

5

30 60 20 20 20

樣例輸出 Copy

80

提示

樣例解釋

選擇區間[2,5],其中gcd(60,20,20,20)=20,故魔力值為(5-2+1)*20=80。

有一個結論是

區間GCD收斂的很快，gcd的種類最多不超過nlogx(x是數的個數)個      

找不到證明了……

然後就可以進行優雅的暴力了~

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
const int maxn=1e5+100;
 
ll n,a[maxn];
 
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
 
map<ll,ll>mp1;
map<ll,ll>mp;
 
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    ll res=0;
    for(int i=1;i<=n;i++){///枚舉右端點
        mp=mp1;///用之前的區間更新這次對于右端點來說gcd的值和位置
        mp1.clear();
        res=max(res,a[i]);///區間長度是1
        if(!mp1.count(a[i])) mp1[a[i]]=i;
        for(auto it=mp.begin();it!=mp.end();it++){
            ll tmp=gcd(a[i],it->first);
            res=max(res,tmp*(i-it->second+1));
            
            if(!mp1.count(tmp)) mp1[tmp]=it->second;///記錄這次對于下一個右端點的資訊
            else mp1[tmp]=min(mp1[tmp],it->second);
            
        }
    }
    cout<<res<<endl;
    return 0;
}