1. 题目
2.Tree
题目描述：
Spray总喜欢搞一些无聊的东西。今天他走在HZ校园小路上，又对那一排小树起了兴趣。Spray数出了每棵树上的叶子个数，有的很少（甚至只有1片叶子），有的却很多。但他认为如果相邻两棵树的叶子个数如果互质是不和谐的。因此Spray想从一排小树中选出若干棵（可不连续），在满足选出的相邻两棵树的叶子个数不互质的条件下，使得树尽量多。
输入格式 Input Format
第一行一个正整数n，表示有n棵香樟树。
第二行n个正整数，第i个数表示第i棵香樟树叶子的个数。
输出格式 Output Format
一个正整数，表示最多能选多少棵树。
样例输入 Sample Input
6
6 2 3 15 8 5
样例输出 Sample Output
4
注释 Hint
样例解释：选择第1、第3、第4和第6棵树
数据范围
对于30%的数据n<=1000
对于100%的数据 n<=100000，叶子个数<=100000
2. 题目实质
求最长 XX 序列的升级版，显而易见的动态规划。
3. 算法
最长 XX 序列，果断 DP 。
这个题的预处理比较牛 X ，注意，这个题裸 DP ，判断一次更新一次明显会超时。
首先，做出一个素数表，筛法，此处略。
然后，一边读入 x ，一边进行处理，用 f 数组存截止到你读入的那个 x ，最长不互质序列到底有多长，其中 f 数组的每一项表示与这个数有同一个质因子的最长（不互质）序列到底有多长（要先将这个数分解质因数，然后判断），如果有某一个数之前的最长不互质序列的长度超过了 ans ，就更新 ans。
当然，也可以全部读入，然后一起处理。
这个算法有一个缺陷，当 n 很大，而且里面的数全是很大的素数时，每读入一次判断的量太大，显然会超时。此时可以利用一开始生成的那个素数表（ Boolean 的），一上来先判断这个数是不是素数，如果他是素数，那也就不用分解质因数求它的因子了，这样可以对付那种极端数据。（不过此处没有）
4. 注意事项
预处理要做好。
5. 程序代码
Leve & Liukeke （pascal）
var
ff:array[0..100000] of boolean;
b:array[0..100000] of longint;
f:array[0..100000] of longint;
temp:array[0..100000] of longint;
n,i,j,x,tot,max,ans:longint;
begin
assign(input,'tree.in');reset(input);
assign(output,'tree.out');rewrite(output);
n:=100000;
for i:=2 to trunc(sqrt(n))do
for j:=2 to (n div i) do
ff[i*j]:=true;
for i:=2 to n do
if not ff[i] then
begin
inc(b[0]);
b[b[0]]:=i;
end;
readln(n);
ans:=0;
for i:=1 to n do
begin
read(x);
j:=1;
tot:=0;
max:=0;
while b[j]<=x do
begin
if x mod b[j]=0 then
begin
inc(tot);
temp[tot]:=b[j];
if f[b[j]]>max then max:=f[b[j]];
end;
while (x mod b[j]=0) do x:=x div b[j];
inc(j);
end;
if max+1>ans then ans:=max+1;
for j:=1 to tot do
f[temp[j]]:=max+1;
end;
writeln(ans);
close(input);
close(output);
end.