哈哈哈我也有个唐氏做法
也是考虑一个朴素 dp ，设 \(dp_{i}\) 表示以 \(i\) 结尾的字串最长是多少，则容易想到若 \(a_{i-1}\) 和 \(a_i\) 是等比数列的一部分就一定能从 \(dp_{i-1}\) 转移到 \(dp_i\)，证明最后讲
那么如何判断 \(a_{i-1}\) 和 \(a_i\) 是否为等比数列的一部分呢？
首先设 \(d=max(a_i,a_{i-1}),x=min(a_i,a_{i-1}),c=d/x\)
变量名记忆方法
其实就是大，小，除的拼音首字母啦qwq
- 那么首先发现，如果 \(d\%x≠0\) 那就明显不是等比数列的一部分
- 接着考虑 \(d==x\) 的情况，发现若\(dp_{i-1}\) 是通过相同转移的则 \(dp_{i}=dp_{i-1}+1\)，否则 \(dp_{i}=dp_2\)
但是这就很尬了呀，我咋知道 \(dp{i-1}\) 是从那里转移的呢？
没有关系，直接新开一个数组 \(f_i\) 表示 \(dp_i\) 是从哪里转移的（这个数组是一个伏笔） - 最后就是正常情况了，很容易发现若 \(c\) 能拆解成 \(a^b\) ，那么就能转移成功……吗？
发现必须和 \(dp_{i-1}\) 转移来源的 \(a\) 相同，所以fw回收再立用一下，使用 \(f\) 数组来存 \(a\)
最后的细节：和dyc一样离散化来去重
妈
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100100],n,dp[100100],inv[100100],tot=0,b[100100],lyh[100100],yz[170],f[100100],vis[100100],cnt=1;
int qpow(int x,int y){
int aaa=1;
while(y){
if(y&1){
aaa*=x;
}
x*=x;
y>>=1;
}
return aaa;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
int tt=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++){
lyh[i]=lower_bound(b+1,b+1+tt,a[i])-b;
}
//↑离散化
inv[++tot]=2;
for(int i=3;i<=1000;i++){
for(int j=2;j<i;j++){
if(i%j==0){
break;
}
if(j==i-1){
inv[++tot]=i;
}
}
}
//↑预处理1000以内的质数
dp[1]=1;
vis[lyh[1]]=1;
//vis[i]代表 i 是否用过
for(int i=2;i<=n;i++){
int bbh=1;
dp[i]=1;
int x=min(a[i],a[i-1]),d=max(a[i],a[i-1]);
if(d%x){
cnt++;
//cnt表示版本号
vis[lyh[i]]=cnt;
continue;
}
if(d==x){
if(!f[i-1]){
dp[i]=dp[i-1]+1;
}
else{
dp[i]=2;
cnt++;
vis[lyh[i]]=cnt;
}
continue;
}
int c=d/x,t=0,tflag=0;
for(int j=1;j<=tot;j++){
yz[j]=0;
}
int maxn=0;
for(int j=1;j<=tot;j++){
while(c%inv[j]==0){
yz[j]++;
c/=inv[j];
}
maxn=max(maxn,yz[j]);
}
//↑分解质因数
if(c!=1){
cnt++;
vis[lyh[i]]=cnt;
continue;
}
for(int k=1;k<=maxn;k++){
int flag=1,sum=1;
for(int j=1;j<=tot;j++){
if(yz[j]%k){
flag=0;
break;
}
sum*=qpow(inv[j],yz[j]/k);
if(sum>1000){
flag=0;
break;
}
}
if(flag){
tflag=1;
f[i]=sum;
if((sum==f[i-1]||!f[i-1])&&vis[lyh[i]]!=cnt){
dp[i]=dp[i-1]+1;
vis[lyh[i]]=cnt;
}
//↑成功转移
}
}
if(tflag){
if(dp[i]<2){
dp[i]=2;
cnt++;
vis[lyh[i]]=cnt;
}
}
else{
cnt++;
vis[lyh[i]]=cnt;
}
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
return 0;
}