[9.28模拟] good-白红宇

[9.28模拟] good

阅读量：6969 次

发布时间：2019-06-27

本文共 1192 字，大约阅读时间需要 3 分钟。

题意：给出一个单调递增的序列{

\(a_i\)}，要你构造一个序列{

\(x_i\)}，使得：

1、\(x_i\in{\{a_i}\}\)

2、\(\{x_i\}\)单调递增

3、\(gcd(x_i,x_i+1)>1\)

求出最长的\(\{x_i\}\)序列

题解：

dp[i]表示选第i个数的最大长度

显然可以\(n^2\)的实现

考虑如何优化

利用gcd的性质，一个数只会被与它有公共质因子的数转移到，所以当一个数要被与它某一个质因子相同的数转移时，我们只需要考虑已知贡献最大的那个数即可

所以分解出每个数的质因子，利用每一个质因子作为代表进行转移即可

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long long#define N 100010using namespace std;int n,cnt,ans,dp[N],pri[N],a[N],c[N];bool mark[N];vector
           
             ve[N];int gi() { int x=0,o=1; char ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') o=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return o*x;}void pre() { for(int i=2; i<=100000; i++) { if(!mark[i]) pri[++cnt]=i; for(int j=1; j<=cnt && i*pri[j]<=100000; j++) { mark[i*pri[j]]=1; if(i%pri[j]==0) break; } } for(int j=1; j<=cnt; j++) for(int i=pri[j]; i<=100000; i+=pri[j]) ve[i].push_back(pri[j]); }int main() { n=gi(); pre(); for(int i=1; i<=n; i++) a[i]=gi(); for(int i=1; i<=n; i++) { int siz=ve[a[i]].size(); for(int j=0; j