Shine on You Crazy Diamond

zunaed BUET Inter University Pro...
Limits 1s, 512 MB

This problem is authored by one of our late friends, Sifat, who unexpectedly left us last year. He was a brilliant programmer, an astute philosopher and an amazing human being. Had he been with us, he would have been delighted to see this year’s brilliant IUPC coming to life and would wish you good luck for the contest. We sincerely hope you enjoy his problem.

You are given an array aa of size nn. You can select a number x>1x > 1 (xx may or may not be an element of aa) and remove every multiple of xx from the array. You need to find the minimum size of the array aa after performing this operation exactly twice.


The first line contains an integer, n(1n105)n (1 \leq n \leq 10^5).

The second line contains nn space-separated integers a1,a2,,an(1ai106)a_1, a_2, \cdots, a_n (1 \leq a_i \leq 10^6).


On the first line, output a single integer, the minimum size of array aa after performing this operation exactly twice.

On the second line, output two integers x1x_1 and x2x_2 (2x1,x22311)(2 \leq x_1, x_2 \leq 2^{31}-1), the chosen values of xx for the two operations.


4 8 25 21
4 21

You can chose 4 and remove 4 8 to get the new array 25 21. Then you can chose 25 to get the new array 21 . So the answer is 1.

There exists other choices that can give the same result too. For example 2 3 is a valid solution as well.

2 4 6
2 1605113

If you choose 2 first, all elements are removed after the first move. Then you can choose any integer for the second move. As such 2 xx for any 2x23112 \leq x \leq 2^{31}-1 is a valid output.


Login to submit.



54% Solution Ratio
rkb_rdEarliest, 6d ago
user.787223Fastest, 0.0s
Soumya1Lightest, 6.3 MB
RF_FaisalShortest, 1107B
Toph uses cookies. By continuing you agree to our Cookie Policy.