codeforce 246B——Good Sequences

矫情吗；* 2022-08-11 04:58 122阅读 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;
    }