CF1043F.Make It One

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Janusz is a businessman. He owns a company "Januszex", which produces games for teenagers. Last hit of Januszex was a cool one-person game "Make it one". The player is given a sequence of nn integers aia_i .

It is allowed to select any subset of them, and the score is equal to the greatest common divisor of selected elements. The goal is to take as little elements as it is possible, getting the score 11 . Now Janusz wonders, for given sequence, how much elements should the player choose?

输入格式

The first line contains an only integer nn ( 1n3000001 \le n \le 300\,000 ) — the number of integers in the sequence.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n ( 1ai3000001 \le a_i \le 300\,000 ).

输出格式

If there is no subset of the given sequence with gcd equal to 11 , output -1.

Otherwise, output exactly one integer — the size of the smallest subset with gcd equal to 11 .

输入输出样例

  • 输入#1

    3
    10 6 15
    

    输出#1

    3
    
  • 输入#2

    3
    2 4 6
    

    输出#2

    -1
    
  • 输入#3

    7
    30 60 21 42 70 15 30
    

    输出#3

    3
    

说明/提示

In the first example, selecting a subset of all numbers gives a gcd of 11 and for all smaller subsets the gcd is greater than 11 .

In the second example, for all subsets of numbers the gcd is at least 22 .

首页