codeforce 246B——Good Sequences-蒲公英云

codeforce 246B——Good Sequences

矫情吗；* 2022-08-11 04:58 307阅读 0赞

第一次的尝试的思路是，用dp进行进行搜索，不过在第21组TLE，这也很正常。因为为复杂度是O(n^2),而n的最大值为为10^5.

第二次尝试把所给的数进行素性拆分、定义flag数组，表示前面的每个数对应的最长序列的长度，统计素因子的对应的长度最大值，然后再用素因子的最大值更新所有素因子的长度值。然后数据读完答案就出来了。不过n=1要特殊处理。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100005;
int prime[maxn],flag[maxn],num;
void sieve()
{
    memset(flag,0,sizeof(flag));
    int i,j;
    for(i=2;i*i<=maxn;i++)
        if(!flag[i])
            for(j=i*i;j<=maxn;j+=i)
                flag[j]=1;
} 
int gen_prime()
{
    sieve();
    flag[0]=1,flag[1]=1;
    int count=0;
    for(int i=2;i<=maxn;i++)
        if(!flag[i])
            prime[count++]=i;
        return count;
}
int main()
{
    int n,cnt;
    cnt=gen_prime();//生成10w以内的素数、并统计素数的个数；不过因为CF单组判断，所以浪费了时间。
    while(scanf("%d",&n)==1)
    {
        memset(flag,0,sizeof(flag));
        for(int i=1;i<=n;i++)
            {
                scanf("%d",&num);
                int ans=0,tmp=num;
                for(int j=0;j<cnt&&tmp!=1;j++)
                {
                    if(tmp%prime[j]==0)//查找素因子对应的长度最大值
                        {
                            flag[prime[j]]++;
                            while(tmp%prime[j]==0)
                            tmp/=prime[j];
                            if(ans<flag[prime[j]])ans=flag[prime[j]];
                        }
                }
                for(int j=0;j<cnt&&num!=1;j++)
                {
                    if(num%prime[j]==0)//更新素因子对应值
                        flag[prime[j]]=ans;
                    while(num%prime[j]==0)
                        num/=prime[j];
                }
            }
            int anwser=0;
            if(n==1)anwser=1;
            else 
            {
                for(int j=0;j<cnt;j++)
                    if(anwser<flag[prime[j]])anwser=flag[prime[j]];
            }
        printf("%d\n",anwser);
    } 
    return 0;
}