题目概述

如果一棵二叉树儿子和祖先权值均互质则是一棵FFT（手动滑稽），现在给出一棵树权值的中序遍历，问是否有一种方案使得该树为FFT。

解题报告

首先有结论：如果 $[L,R]$ 可以变成FFT，那么随便选一个合法的作为根都是可以的，画画中序遍历发现挺显然的……

问题是怎么求出每个点是否与 $[L,R]$ 中其他点均互质，套路：$i$ 质因数分解之后每个因子最近出现的位置中最近的位置就是 $i$ 能到达的最远位置。至于质因数分解可以用线性筛筛出最小素因子。

但是就算这样，每次也不可能暴力找一个合法的根？你错了……就是可以暴力找，只要从两端一起开始找就可以，为什么呢？由于是从两端开始找，所以近的一段会先遇到合法的根，次数是合法的根到端点的距离，这可以看作小的块往大的块合并，是启发式合并的逆过程（启发式分裂？），所以复杂度是正常的。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=1000000,maxa=10000000,maxp=664579;

int n,a[maxn+5],pre[maxn+5],nxt[maxn+5],pos[maxp+5],fa[maxn+5];
int D[maxa+5],p[maxp+5];bool pri[maxa+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r))?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline void Make(){
    for (int i=2;i<=maxa;i++){
        if (!pri[i]) p[++p[0]]=i,D[i]=p[0];
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=maxa;j++)
            {D[t]=D[i];pri[t]=true;if (!(i%p[j])) break;}
    }
}
bool Dfs(int L,int R,int p=0){
    if (L>R) return true;
    for (int l=L,r=R;l<=r;l++,r--){
        if (R<=nxt[l]&&pre[l]<=L) return fa[l]=p,Dfs(L,l-1,l)&&Dfs(l+1,R,l);
        if (R<=nxt[r]&&pre[r]<=L) return fa[r]=p,Dfs(L,r-1,r)&&Dfs(r+1,R,r);
    }return false;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    Make();readi(n);for (int i=1;i<=n;i++) readi(a[i]);
    for (int i=1;i<=p[0];i++) pos[i]=-1;
    for (int i=1;i<=n;i++){
        pre[i]=1;for (int x=a[i];x>1;x/=p[D[x]]) pre[i]=max(pre[i],pos[D[x]]+1);
        for (int x=a[i];x>1;x/=p[D[x]]) pos[D[x]]=i;
    }
    for (int i=1;i<=p[0];i++) pos[i]=n+1;
    for (int i=n;i;i--){
        nxt[i]=n;for (int x=a[i];x>1;x/=p[D[x]]) nxt[i]=min(nxt[i],pos[D[x]]-1);
        for (int x=a[i];x>1;x/=p[D[x]]) pos[D[x]]=i;
    }
    if (Dfs(1,n)) {for (int i=1,fst=true;i<=n;i++) fst?fst=false:putchar(' '),printf("%d",fa[i]);}
    else puts("impossible");return 0;
}