#A. 序列

    Type: Default 1000ms 256MiB

序列

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

序列

题目限制

1000 ms 256 M

题目描述

YY 酷爱的接龙游戏正是这样。玩腻了成语接龙之后,小 YY 决定尝试无平方因子二元合数接龙,规则如下:

现有 nn 个不超过 10610^6 的合数,每个均可表示为 a=pqa=p*q ( p,qp,q 为两个互异素数)。

a=p1q1(p1<q1)a=p_1*q_1(p_1\lt q_1),b=p2q2(p2<q2)b=p_2*q_2(p_2\lt q_2)当且仅当 q1=p2q_1=p_2bb 能接在 aa 后面。

请问从给定的这 nn 个数中选数接龙,最长可以形成一个包含多少数的接龙序列?

输入格式

第一行输入一个正整数 n,意义如题干所述。(n≤50000) ​第二行输入 n 个不超过 10^6 的合数。

输出格式

输出仅一个整数,表示问题的答案。

数据范围

测试点 131\sim 3 满足:n=9n=9,每个数不超过 10001000;

测试点 464\sim 6 满足:n=1000n=1000,每个数不超过 10610^6;

测试点 7107\sim 10 满足:n=50000n=50000,每个数不超过 10610^6

输入样例

9
10 6 22 15 21 35 77 119 187

输出样例

5

样例解释

最长接龙为 {6(23),15(35),35(57),77(711),187(1117)}\{6(2*3),15(3*5),35(5*7),77(7*11),187*(11*17)\},长度为 55

NOIP模拟赛1

Not Attended
Status
Done
Rule
OI
Problem
4
Start at
2022-11-12 8:00
End at
2022-11-12 12:00
Duration
4 hour(s)
Host
Partic.
37