【BZOJ】【4052】【CERC2013】Magical GCD

时间：2021-01-15 19:42:39

DP/GCD

　　然而蒟蒻并不会做……

　　Orz @lct1999神犇

　　首先我们肯定是要枚举下端点的……嗯就枚举右端点吧……

　　那么对于不同的GCD，对应的左端点最多有log(a[i])个：因为每次gcd缩小，至少变成gcd/2（2是最小的质因数），所以是log个左端点……

　　所以我们就有了log段！每段的gcd是相同的。当我们加入一个新的右端点时，除了该节点本身外，不会出现新的左端点，原有的左端点可能会不变，或是两(多)段合并成一段，用滚动数组记一下，暴力搞就可以了……$O(n*log^2n)$

Orz lct1999，我WA了的原因：

　　1.每组数据还是需要清一下tot数组的，不能光靠加新点的时候清tot[i&1]，第一个点应该把tot[0]也清掉。

　　2.每次是更新这一段的gcd，所以是要记录gcd的，不能光记个端点，每次求两个端点的gcd……这明显不对啊好吗= =

蒟蒻果然好弱啊……退OI保平安吧QAQ

 /**************************************************************

     Problem: 4052

     User: Tunix

     Language: C++

     Result: Accepted

     Time:820 ms

     Memory:5180 kb

 ****************************************************************/

 //BZOJ 4052

 #include<vector>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 typedef long long LL;

 LL getLL(){

     LL v=,sign=; char ch=getchar();

     while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 const int N=,INF=~0u>>;

 /*******************template********************/

 LL a[N],f[][N],b[][N],n;

 int tot[];

 inline LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("input.txt","r",stdin);

 //  freopen("output.txt","w",stdout);

 #endif

     int T=getLL(),now;

     while(T--){

         n=getLL();

         tot[]=tot[]=;

         LL ans=;

         F(i,,n){

             now=i&;

             tot[now]=;

             a[i]=getLL();

             F(j,,tot[now^]){

                 int k=b[now^][j];

                 if ( j> && gcd(a[i],f[now^][j])==gcd(a[i],f[now^][j-]) ) continue;

                 b[now][++tot[now]]=b[now^][j];

                 f[now][tot[now]]=gcd(a[i],f[now^][j]);

                 ans=max(ans,f[now][tot[now]]*(i-k+));

             }

             if (f[now][tot[now]]!=a[i]){

                 b[now][++tot[now]]=i;

                 f[now][tot[now]]=a[i];

             }

 //          F(j,1,tot[now]) printf("%lld ",b[now][j]); puts("");

 //          F(j,1,tot[now]) printf("%lld ",f[now][j]); puts("");

             ans=max(ans,a[i]);

         }

         printf("%lld\n",ans);

     }

     return ;

 }

4052: [Cerc2013]Magical GCD

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 146  Solved: 68
[Submit][Status][Discuss]

Description

给出一个长度在 100 000 以内的正整数序列，大小不超过 10^12。 
求一个连续子序列，使得在所有的连续子序列中，它们的GCD值乘以它们的长度最大。

Input

Output

Sample Input

1
5
30 60 20 20 20

Sample Output

80

HINT

Source

[Submit][Status][Discuss]

相关文章