传送门
发现这题选或不选对状态的优劣程度不会产生影响，如果已经确定了两个数a和b，那么最优的首项和公比也都是唯一确定的，
与对于后面的数x，加进去也好不加进去也好，首项和公比依旧是原来的
于是我们用尺取算法，用两个指针来扫一遍，
如果只有一个数且下一个数能被整除，就加进去，然后确定首项和公比
如果只有一个数且下一个数不能整除，两个指针直接指向下一个数
如果有多个数且下一个数满足公式，就加进来
如果有多个数且下一个数不满足公式，两个指针直接指向下一个数
这样对于最优解，一定是可以找到的
顺便说下最优的公比和首项的确定：
已知两个数x y，求满足它们的最优的首项 公比
设x=a*q^k1 y=a*q^k2 且x>y
那么x/y得到q^(k1-k2)，
由于最优的公比一定尽可能小，所以要使指数尽可能大，就把q质因数分解，指数取gcd提出
这样就得到了公比，拿这个公比不断地除以一开始的x，就得到了首项
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<vector>
#define INF 0x7f7f7f7f
#define pii pair<int,int>
#define ll long long
#define MAXN 100005
using namespace std; ll read(){
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if('-'==ch)f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n;
set<ll> s;
ll a[MAXN];
int gcd(int x,int y){
return (y==?x:gcd(y,x%y));
}
ll Pow(ll x,ll y){
ll ret=;
while(y){
if(y&){
ret*=x;
}
x*=x;
y>>=;
}
return ret;
}
int gt(ll x,ll y,ll &b,ll &q){
ll t=x/y;
if(==t){
b=x,q=;
return ;
}
vector<pii> vs;
for(int i=;i<=;i++){
if(t%i==){
int cnt=;
while(t%i==){
cnt++;
t/=i;
}
vs.push_back(make_pair(i,cnt));
}
}
if(t>){
return -;
}
int g=vs[].second;
for(int i=;i<vs.size();i++){
g=gcd(g,vs[i].second);
}
q=;
for(int i=;i<vs.size();i++){
q*=Pow((ll)vs[i].first,(ll)vs[i].second/g);
}
b=y;
while(b%q==){
b/=q;
}
return ;
}
int check(ll x,ll b,ll q){
if(x%b){
return ;
}
if(q==){
return (x==b);
}
if(s.count(x)){
return ;
}
x/=b;
ll t=q;
int L=,R=log(1.0*x)/log(1.0*q)+;
while(R-L>){
int mid=(L+R)/;
ll t=Pow(q,(L+R)/);
if(t>=x){
R=mid;
}
else{
L=mid;
}
}
if(Pow(q,L)==x||Pow(q,R)==x){
return ;
}
return ;
}
int main()
{
// freopen("seq2.in","r",stdin);
// freopen("seq.out","w",stdout);
n=read();
for(int i=;i<=n;i++){
a[i]=read();
}
int L=,R=;
int ans=;
ll b=,q=;
s.insert(a[]);
for(int i=;i<=n;i++){
ll t1=a[R],t2=a[i];
if(t1<t2){
swap(t1,t2);
}
if(t1%t2!=){
s.clear();
s.insert(a[i]);
L=i,R=i;
continue;
}
if(L==R){
R++;
s.insert(a[R]);
if(-==gt(t1,t2,b,q)){
L++;
s.clear();
s.insert(a[L]);
}
}
else if(check(a[i],b,q)){
R++;
if(q!=)
s.insert(a[R]);
}
else{
s.clear();
s.insert(a[i]);
L=i,R=i;
}
ans=max(ans,R-L+);
}
printf("%d\n",ans);
return ;
}