【gcd+stl】UVa1642 Magical GCD-白红宇

【gcd+stl】UVa1642 Magical GCD

阅读量：5360 次

发布时间：2019-06-15

本文共 1178 字，大约阅读时间需要 3 分钟。

Description

　　一个长度为n的数列，选一个连续子序列，使得子序列的公约数*长度最大，求这个最大值。n<=1e5。

Solution

　　连续子序列一般都要用滑动窗口是吧(固定r，快速计算最优l，从r转移到r+1时无需重新计算l信息)

　　对于一个r，l递减时gcd也一定递减或不变，所以gcd最多有log(a[i])种不同取值　

　　那么对于每一个相同的gcd，显然只需要保存最小的l

　　转移也很方便，反正最多log种元素，直接每一个暴力转移，有删除、添加、更新操作，用map来水再好不过了。

　　大白例题。

Code

　　不太会map...现在才知道first&second...膜了一发别人的代码...

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
         5 #define ll long long 6 using namespace std; 7  8 map
         
          a; 9 ll n,x,ans;10 11 ll gcd(ll x,ll y){
   return y==0?x:gcd(y,x%y);}12 13 int main(){14     int T;15     scanf("%d",&T);16     while(T--){17         scanf("%lld",&n);18         a.clear();19         ans=0;20         for(int i=1;i<=n;i++){21             scanf("%lld",&x);22             if(!a.count(x)) a[x]=i;23             for(map
          
           ::iterator it=a.begin();it!=a.end();){24 ll tmp=gcd(x,it->first);25 ans=max(ans,tmp*(i-it->second+1));26 if(!a.count(tmp))27 a[tmp]=it->second;28 else29 a[tmp]=min(a[tmp],it->second);30 if(tmp
           
            first)31 a.erase(it++);32 else it++;33 }34 }35 printf("%lld\n",ans);36 }37 return 0;38 }