CF 264B(质因数分解)

D. Good Sequences

time limit per test

memory limit per test

input

output

n 有 a₁, a₂, ..., a_n

问删后序列最长长度.

Input

n (1 ≤ n ≤ 10⁵) 第二行序列 a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁵; a_i < a_i + 1).

Output

删后序列最长长度.

Sample test(s)

input

5 2 3 4 6 9

output

4

input

9 1 2 3 5 6 7 8 9 10

output

4

Note

In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.

错解：枚举开头即可。X

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (100000+10)
int n,a[MAXN];
bool b[MAXN]={0};
int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);};
int main()
{
  scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
  int ans=0;
  for (int i=1;i<=n;i++)
  if (!b[i])
  {
    int len=1;
    b[i]=1;
    int head=i,tail=i+1;
    while (tail<=n)
    {
      if (gcd(a[tail],a[head])==1) tail++;
      else {b[head]=1;head=tail;tail++;len++;  }
    }
    ans=max(ans,len);
  }
  cout<<ans<<endl;
    
  return 0;
}

更正：

枚举开头不行，因为一个开头可能跟有多个序列（2，6，9）/（2，4）←选这个不忧

故枚举质因数，证明下：

若a和b不互质,则必存在质数k，使k|a&&k|b

故Dp如下:

 f[i,j]=max(f[i-1,k]+1) (k| a[i] 且j|a[i] ) 最大值len=f[i,j] 

//  f[i,j]  表示到第i个数为止，结尾是质数 j 的倍数的最大长度。

+上滚动数组后，得到如下的Dp方程

计算： len=max(f[k])+1 (k| a[i] )

更新：f[j]=max(f[j],len) (j|a[i])​ 

注意质因数的分解中 先分解到√n，若此时未除尽，那一部分也要算进去（肯定是质数，否则必能再分）

eg：14=2*7（7=√49>√14）

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (100000+10)
int n,a[MAXN],f[MAXN]={0},st[MAXN],size;
int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);};
void fac_prime(int x)
{
  size=0;
  for (int j=2;j*j<=x;j++)
  {
    if (x%j==0)
    {
      while (x%j==0) x/=j;
      st[++size]=j;
    }
  }
  if (x>1) st[++size]=x;
}
int main()
{
  scanf("%d",&n);
  int ans=0;
  for (int i=1;i<=n;i++)
  {
    scanf("%d",&a[i]);
    if (a[i]==1) {ans=max(ans,1);continue;}
    fac_prime(a[i]);
    int len=0;
    if (st[1]==a[i]) {len=1;f[a[i]]=1;}
    else 
      for (int j=1;j<=size;j++) 
        len=max(len,f[st[j]]+1);
    
    for (int j=1;j<=size;j++) f[st[j]]=max(f[st[j]],len);
    ans=max(ans,len);    
//    for (int j=1;j<=a[i];j++) cout<<f[j]<<' ';
//    cout<<endl; 
  }  
  cout<<ans<<endl;
  return 0;
}