Solutions Codeforces Round #830 (Div. 2) Editorial
Codeforces Round #830 (Div. 2) Editorial Thanks for the participation! 1732A - Bestie Let's make an important observation: gcd ( n − 1 , n ) = 1 gcd ( n − 1 , n ) = 1 for any value of n n . Moreover, choosing i = n − 1 i = n − 1 and i = n i = n are the cheapest operations. From this we can conclude that the answer is ≤ 3 ≤ 3 . Let g g be the gcd gcd of all numbers in the array. Then we have the following cases: If g = 1 g = 1 , then the operation can be omitted and the answer is 0 0 , Otherwise, let's try the cheapest operation i = n i = n . If gcd ( g , n ) = 1 gcd ( g , n ) = 1 , then the answer is 1 1 . Otherwise, let's try the next cheapest operation, ie i = n − 1 i = n − 1 . If gcd ( g , n − 1 ) = 1 gcd ( g , n − 1 ) = 1 , then the answer is 2 2 . Otherwise, the answer is 3 3 , since gcd ( g , n − 1 , n ) = 1 gcd ( g , n − 1 , n ) = 1 . 1732B - ...