#include<bits/stdc++.h>
using namespace std;
const int N=1e7;
int n,cnt,a[200005],f[700000],num[N+5],dp[N+5];
bool prime[N+5];
void getprime(){
memset(prime,true,sizeof(prime));
prime[0]=prime[1]=false;
for(int i=2;i<=N;i++){
if(prime[i]) f[++cnt]=i;
for(int j=1;j<=cnt&&i*f[j]<=N;j++){
prime[i*f[j]]=false;
if(i%f[j]==0) break;
}
}
return;
}
int main(){
freopen("item.in","r",stdin);
freopen("item.out","w",stdout);
getprime();
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
num[a[i]]++;
}
for(int i=1;i<N;i++){
dp[i]=max(dp[i],num[i]);
for(int j=1;i*f[j]<N&&j<=cnt;j++){
dp[j]=max(dp[j],num[j]+dp[i]);
}
}
int ans=0;
for(int i=1;i<N;i++) ans=max(ans,dp[i]);
printf("%d",ans);
return 0;
}
样例过了吗？
转移公式错了，num是看他有没有出现过，所以不能num[j]+dp[j]，转移方程应该是dp[a[i]]=max(dp[a[i]],dp[j]+1),如果另一个和他成对的因数也出现过，在转移dp[a[i]]=max(dp[a[i]],dp[a[i]/j]+1)（注意排除完全平方数的情况）
没看懂，我这是在更新后面的状态，按照老师的思路来的，要不你把循环整个发出来？
差不多懂了，就是枚举 a_i 的所有因子，如果之前出现过这个数，就更新 f 数组，如果另一个对应的因子也出现过且不是完全平方数，也更新，对吧？
那就不用筛质数了？
你可要可不要（看你自己）
不用，这就够了