307235: CF1325E. Ehab's REAL Number Theory Problem

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Ehab's REAL Number Theory Problem

题意翻译

给一些数,每个的因数个数不超过 $7$,求最少选出多少个,使得乘积为完全平方。无解输出 $-1$。

题目描述

You are given an array $ a $ of length $ n $ that has a special condition: every element in this array has at most 7 divisors. Find the length of the shortest non-empty subsequence of this array product of whose elements is a perfect square. A sequence $ a $ is a subsequence of an array $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) elements.

输入输出格式

输入格式


The first line contains an integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of $ a $ . The second line contains $ n $ integers $ a_1 $ , $ a_2 $ , $ \ldots $ , $ a_{n} $ ( $ 1 \le a_i \le 10^6 $ ) — the elements of the array $ a $ .

输出格式


Output the length of the shortest non-empty subsequence of $ a $ product of whose elements is a perfect square. If there are several shortest subsequences, you can find any of them. If there's no such subsequence, print "-1".

输入输出样例

输入样例 #1

3
1 4 6

输出样例 #1

1

输入样例 #2

4
2 3 6 6

输出样例 #2

2

输入样例 #3

3
6 15 10

输出样例 #3

3

输入样例 #4

4
2 3 5 7

输出样例 #4

-1

说明

In the first sample, you can choose a subsequence $ [1] $ . In the second sample, you can choose a subsequence $ [6, 6] $ . In the third sample, you can choose a subsequence $ [6, 15, 10] $ . In the fourth sample, there is no such subsequence.

Input

题意翻译

给一些数,每个的因数个数不超过 $7$,求最少选出多少个,使得乘积为完全平方。无解输出 $-1$。

加入题单

上一题 下一题 算法标签: