GCD&LCM（HG 2018.5.13 T2）

 第一问：如果存在 GCD(A i ,A i+1 ) = 1，答案为数列长度 N；否则无解，答案为 -1。 第二问： 解法一：动态规划 令 f[i] 表示以第 i 个数作为结尾，最长满足条件的序列的长度。 f[i]=min(f[i-1]+1,i-k+1) 其中 k 表示最后一个不与 A i 互质的数的序号。 答案就是 max{f[1],f[2],...,f[n]}。 时间复杂度为 O(n)。 解法二：维护队列 维护一个这样的队列：使得队中的元素两两互质。 从左到右，每次将元素 A i 入队，如果队列中的元素不两两互质，就让队首出队，直到满足 两两互质为止。 并且记录每次队列中的元素个数，记作 S i 。 答案就是 max{S i }(i = 1,2,...,n)。 时间复杂度依然是 O(n)。 以下是队列的方法 ```cpp #include<map> #include<set> #include<list> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int read() { int x=0,flag=0; char ch=getchar(); if(ch=='-') flag=1; while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x*=10,x+=ch-'0',ch=getchar(); if(flag) return -x; return x; } int write(int x) { if(x<0) putchar('-'); if(x>=10)write(x/10); putchar(x%10+'0'); } int T,n,a[101000]; int l,r,cnt=0; int f[1000100],vis[1000100];//f[i]记录的质数i是否出现过 int p[1000100],fac[1000100];//p记录的是素数，fac[i]记录的是i的最小的质因数 void get_prime()//处理出p和fac { for(int i=2;i<=1e6;i++) { if(!vis[i]) p[++cnt]=i,fac[i]=i; for(int j=1;j<=cnt && p[j]*i<=1e6;j++) { vis[p[j]*i]=1; fac[p[j]*i]=p[j]; if(i%p[j]==0) break; } } } int gcd(int x,int y) { if(!y) return x; return gcd(y,x%y); } bool check(int x) { while(x>1) { if(f[fac[x]]>0) return 0; x/=fac[x]; } return 1; } void del(int x) { while(x>1) { f[fac[x]]--; x/=fac[x]; } } void add(int x) { while(x>1) { f[fac[x]]++; x/=fac[x]; } } int main() { freopen("gm.in","r",stdin); freopen("gm.out","w",stdout); T=read(); get_prime(); for(int t=1;t<=T;t++) { n=read(); int l1=-1,l2=-1; for(int i=1;i<=n;i++) { a[i]=read(); if(i>1) if(gcd(a[i],a[i-1])==1) l1=n;//不多讲，见上面 } int l=1,r=1,i; memset(f,0,sizeof(f)); add(a[1]); while(r<n) { r++; while(!check(a[r])) del(a[l]),l++;//如果进不来就一直弹队首，知道满足要求可以进来了为止 add(a[r]); l2=max(l2,r-l+1); } if(l2==1) l2=-1; printf("Case %d: ",t); printf("%d %d\n",l1,l2); } fclose(stdin); fclose(stdout); return 0; } ```