GCD&LCM(HG 2018.5.13 T2)

2018-05-13 19:08:04


第一问:如果存在 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)。

以下是队列的方法

#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;
}