主要是标记前面素数的最大的DP值,要认真一些。没想到居然写了一个很难发现的错误。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <iostream>
using namespace std;
int o[];
int prim[];
int p[];
int sp[];
int flag[];
int main()
{
int i,j,n,num = ;
int temp,maxz;
for(i = ; i <= ; i ++)
{
if(!o[i])
{
sp[i] = num;
for(j = i+i; j <= ; j += i)
o[j] = ;
prim[num++] = i;
}
}
scanf("%d",&n);
for(i = ; i < n; i ++)
scanf("%d",&p[i]);
if(n == )
{
printf("1\n");
return ;
}
for(i = ; i < n; i ++)
{
maxz = ;
temp = p[i];
for(j = ; j < ; j ++)
{
if(temp == ) break;
if(temp%prim[j] == )
{
maxz = max(maxz,flag[j]);
while(temp%prim[j] == )
{
temp /= prim[j];
}
}
}
if(temp != )
maxz = max(maxz,flag[sp[temp]]);
temp = p[i];
for(j = ; j < ; j ++)
{
if(temp == ) break;
if(temp%prim[j] == )
{
flag[j] = maxz + ;
while(temp%prim[j] == )
{
temp /= prim[j];
}
}
}
if(temp != )
flag[sp[temp]] = maxz + ;
}
maxz = ;
for(i = ;i < num;i ++)
{
maxz = max(maxz,flag[i]);
}
printf("%d\n",maxz);
return ;
}