你魔要火

· · 题解

666 AC。

考虑一个显然的 dp：

f_i=\min\limits_{j<i,a_j<a_i,(a_j,a_i)>1}f_{j-1}

直接写是 O(n^2\log v) 的，显然会 t。

考虑对其进行优化，我们可以枚举 p|a_i，然后就转化为

f_i=\min_{p|a_i}\min_{j<i,a_j<a_i,p|a_j}f_{j-1}

考虑后面这个式子，明显可以用权值线段树做，对 a 离散化的话查询是 O(\log n)。

那么我们对于每个质因子，维护一颗权值线段树，并且每次计算完 f_{i-1} 后，枚举 p|a_i 在 p 对应的权值线段树上在 a_i 处更新 f_{i-1}。注意到每次更新的时候其实只有 O(\log n) 个结点受到影响，那么采用动态开点线段树就可以把空间控制在 O(n\omega(v)\log n)，其中 \omega(n) 表示 n 的不同质因子数。

最后对于质因子分解，我们考虑一个简单的优化，在暴力分解的基础上线性筛出质数，然后试除法就可以只用 \sqrt v 以内的质因子去试，这样复杂度可以少一个 \log v。

这样一来时间复杂度就是 O(n\pi(\sqrt v)+n\omega(v)\log n)，空间是 O(n\omega(v)\log n)，轻松通过。

// Problem: P7810 [JRKSJ R2] Upper
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7810?contestId=48251
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define endl '\n' 
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int P=998244353;
void chkmax(int &x,int y){if(x<y)x=y;}
void chkmin(int &x,int y){if(x>y)x=y;}
int qpow(int a,int k){
    int ret=1;
    while(k){
        if(k&1)ret=ret*(long long)a%P;
        a=a*(long long)a%P;
        k>>=1;
    }
    return ret;
}
int qpow(int a,int k,int p){
    int ret=1;
    while(k){
        if(k&1)ret=ret*(long long)a%p;
        a=a*(long long)a%p;
        k>>=1;
    }
    return ret;
}
int norm(int x){return x>=P?x-P:x;}
int reduce(int x){return x<0?x+P:x;}
void add(int&x,int y){if((x+=y)>=P)x-=P;}
struct IO_Tp {
    const static int _I_Buffer_Size = 2 << 22;
    char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer, *_I_end= _I_Buffer + _I_Buffer_Size;

    const static int _O_Buffer_Size = 2 << 22;
    char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;

    IO_Tp() { fread(_I_Buffer, 1, _I_Buffer_Size, stdin); }
    ~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }

    IO_Tp &operator>>(int &res) {
        int f=1;
        while (_I_pos!=_I_end&&!isdigit(*_I_pos)&&(*_I_pos)!='-') ++_I_pos;
        assert(_I_pos!=_I_end);
        if(*_I_pos=='-')f=-1,++_I_pos;
        res = *_I_pos++ - '0';
        while (_I_pos!=_I_end&&isdigit(*_I_pos)) res = res * 10 + (*_I_pos++ - '0');
        res*=f;
        assert(_I_pos!=_I_end);
        return *this;
    }

    IO_Tp &operator>>(string &res){
        res="";
        auto blank=[&](char ch){
            if(ch==' '||ch=='\n'||ch=='\r'||ch=='   '||ch=='\0')return 1;
            return 0;
        };
        while(_I_pos!=_I_end&&blank(*_I_pos)) ++_I_pos;
        while (_I_pos!=_I_end&&!blank(*_I_pos))res += *_I_pos++;
        assert(_I_pos!=_I_end);
        return *this;
    } 

    IO_Tp &operator<<(int n) {
        if(n<0)*_O_pos++='-',n=-n;
        static char _buf[10];
        char *_pos = _buf;
        do
            *_pos++ = '0' + n % 10;
        while (n /= 10);
        while (_pos != _buf) *_O_pos++ = *--_pos;
        return *this;
    }

    IO_Tp &operator<<(char ch) {
        *_O_pos++ = ch;
        return *this;
    }

    IO_Tp &operator<<(string &res){
        for (char ch:res) *_O_pos++ = ch;
        return *this;
    } 
} IO;
const int N=1e5+5;
int n,m,a[N],sa[N],ua[N],f[N],cnt[N],pr[N][10];
int cp,p[N];
bool vst[N];
void init(int n){
    rep(i,2,n){
        if(!vst[i])p[++cp]=i;
        for(int j=1;j<=cp&&i*p[j]<=n;j++){
            vst[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}
void dcp(int id){
    int x=a[id];
    for(int i=1;p[i]*p[i]<=x;i++)if(x%p[i]==0){
        pr[id][++cnt[id]]=p[i];
        while(x%p[i]==0)x/=p[i];
    }
    if(x>1)pr[id][++cnt[id]]=x;
}
unordered_map<int,int>rt;
int tot;
struct node{
    int lc,rc,ma;
}st[N<<5];
void pushup(int k){st[k].ma=max(st[st[k].lc].ma,st[st[k].rc].ma);}
void insert(int&k,int l,int r,int p,int v){
    if(!k)k=++tot;
    if(l==r)return chkmax(st[k].ma,v),void();
    int mid=l+r>>1;
    if(p<=mid)insert(st[k].lc,l,mid,p,v);
    else insert(st[k].rc,mid+1,r,p,v);
    pushup(k);
    return;
}
int ask(int p,int l,int r,int x,int y){
    if(!p)return -2;
    if(x<=l&&r<=y)return st[p].ma;
    int mid=l+r>>1,ret=-2;
    if(x<=mid)chkmax(ret,ask(st[p].lc,l,mid,x,y));
    if(mid<y)chkmax(ret,ask(st[p].rc,mid+1,r,x,y));
    return ret;
}
int main(){
    IO>>n;
    init(1e5);
    rep(i,1,n)IO>>a[i],sa[i]=a[i],dcp(i);
    sort(sa+1,sa+n+1);
    m=unique(sa+1,sa+n+1)-sa-1;
    rep(i,1,n)ua[i]=lower_bound(sa+1,sa+m+1,a[i])-sa;
    memset(f,-1,sizeof f);
    f[0]=0;
    rep(i,1,n){
        rep(j,1,cnt[i]){
            int p=rt[pr[i][j]];
            chkmax(f[i],ask(p,1,m,1,ua[i]-1)+1);
            if(f[i-1]>=0)insert(p,1,m,ua[i],f[i-1]);
            rt[pr[i][j]]=p;
        }
    }
    IO<<f[n]<<endl;
    return 0;
}