Chrysanthemum's Blog

这道题我们只要在暴力的基础上改进一下就可以了，由于gcd的值不多，我们只要记录每个点得到某个gcd连续最左能到哪（贪心），这个用map维护就可以了，然后我们从左往右扫，每次维护一下map。

代码：

#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
int n,k;
ll a[100010],g,ans;
set< pair<ll,int> > st,st1;
map<ll,int> mp;
ll gcd(ll x,ll y){if (!y) return x;else return gcd(y,x%y);}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    st.clear();
    for (int i=1;i<=n;i++)
    {
        st1.clear();
        mp.clear();
        for (set< pair<ll,int> > ::iterator it=st.begin();it!=st.end();it++)
        {
            g=(*it).first;
            k=(*it).second;
            g=gcd(g,a[i]);
            if (!mp[g]||k<mp[g])
                mp[g]=k;
            st1.insert(make_pair(g,mp[g]));
            ans=max(ans,(ll)(i-mp[g]+1)*g);
        }
        if (!mp[a[i]]){st1.insert(make_pair(a[i],i));ans=max(ans,a[i]);}
        st.clear();
        for (set< pair<ll,int> > ::iterator it=st1.begin();it!=st1.end();it++)
            st.insert(*it);
    }
    printf("%lld\n",ans);
}