This is proof of why answer < 3.

Suppose, we have 3 elements x, y, z, with gcd(x, y, z) != 1. Then, after first transformation array will contain elements: gcd(x, y), gcd(x, z), gcd(y, z), Let's call them a = gcd(x, y), b = gcd(x, z), c = gcd(y, z). After second tranformation array will contain elements: gcd(a, b), gcd(a, c), gcd(b, c), we can notice, that:
gcd(a, b) = gcd(gcd(x, y), gcd(x, z)) = gcd(x, y, x, z) = gcd(x, y, z). Doing similar things with gcd(a, c) and gcd(b, c), it turns out, that gcd(a, b) = gcd(a, c) = gcd(b, c) = gcd(x, y, z). That means, that after 2nd transformation array will contain 3 equal numbers greater than 1. I think it's obvious, that answer will be infinity, if array contains 3 equal numbers greater than 1.


Now, if gcd of any tripple of numbers equals one, that means, that we will end in less than 2 transformations (Proof this by yourself)

Edited by author 22.01.2022 15:49

Try this test:
input:
1
8
output:
1

Oddly enough, my solution printed "infinity" in this simple case, but was successful with first 35 tests

Hello, as you can see (http://acm.timus.ru/status.aspx?author=52097 ), my solve cant get AC.

For all my test cases it looks like very good. Probably I have a little bug or something else and I cant find this mistake (WA on test #10). After many hours spenting for this problem I dont know where could it be. Please, give me simple hint or fail testcase.

My solution at work on those tests:

4
1 1 1 1
0

4
3 1 3 3
inf


4
8 12 4 6
inf

6
4 4 2 4 2 2
inf

3
5 3 7
1

3
8 8 3
2

3
32 64 3
2

3
36 225 1225
2

3
16777216 1594323 5764801
1

3
16777216 1594323 11529602
2

6
2365440 2 3 5 7 11
2


It looks like good for big tests too. Please help. What is the #10 test?

Edited by author 03.09.2016 20:56

Edited by author 05.06.2020 17:42

...

This problem may have four answers: inf, 0, 1, 2 :)

Edited by author 18.01.2014 03:05

3
1 1 1
output is 0 and I ignored this condition.