7 人解决,16 人已尝试。
8 份提交通过,共有 172 份提交。
7.9 EMB 奖励。
单点时限: 1.5 sec
内存限制: 256 MB
It is all choosen by Steins Gate!
As a fan of Steins Gate, you made a game with its background. The whole game world is composed of all positive integers. In the game, $1$ represents the public event, prime numbers represent events that affect the world line, and composite numbers represent world lines.
When a prime number $p$ is a factor of the composite number $c$, it means that the event $p$ can affect the world line $c$. If all events affecting a world line occur, you can choose to reach the world line. For example, reaching world line 12 requires events 2 and 3 to occur. Of course, if events 2 and 3 happen, you can reach an infinite number of world lines such as $4,6,8,9,12…$
As a game developer, you know there are $n$ world lines $a_ 1,…,a_n$ you really want to reach. Because of your excellent performance in developing the game, you get the reward opportunity of $len$: you can choose $1$ or any event as the base point $p$, and all events in the closed interval $[p + 1, p + len] $ will happen.
You want to reach all $n$ world lines, and if there are multiple choices, always give priority to the one with a larger base point. If all $n$ world lines can be reached, you should find the largest base point $p$, and you should output the total number of events that will happen (in other words, output the number of primes in $[p+1,p+len]$). Otherwise, just output $-1$ .
The first line contains two positive integers $n、len$,represent the number of world lines and the size of reward, respectively.
The second line contains $n $ positive integers, $a_1,…,a_n $ represents the world line.
An integer $ans$,represents the answer.
2 11 33 35
5
1 10 39
-1
$1\leq n\leq 200$
$1\leq len \leq 4*10^5$
$1< a_i\leq 10^{18}$,$a_i$ are composite numbers
Sample Explanation:
For input1, choose 2 as the base point, all events in [3, 13] will happen, they are 3,5,7,11,13.
For input2, there is no choice.
7 人解决,16 人已尝试。
8 份提交通过,共有 172 份提交。
7.9 EMB 奖励。
创建: 2 年,10 月前.
修改: 2 年,10 月前.
最后提交: 1 年,11 月前.
来源: N/A