Editorial for Interactive GCD

If number of subsequences with GCD 1 is odd, then the game will never end in a draw. So we have to check whether number of subsequences with GCD 1 is odd or even.

Subtask 1-2: You can calculate the results for each possible combinations and hard code the results. It is possible to discover the array with at most 10 queries in these subtasks.

Subtask 3: We are counting number of subsequences with GCD 1 is, this can be enterpreted as total subsequences - number of subsequences with GCD>=0.
As number of subsequences is always odd, we can say if number of subsequences with GCD>1 is odd then the result is "Yes" otherwise "No". .

Subtask 4: numbers are in range[1,100], in 1-100 range, numbers that will contribute to our result is 60. So we will find those 60 numbers and query only for them. Consider learning about Mobius function.


58% Solution Ratio

DibyaJyotiEarliest, Jul '20

ME_sadmanFastest, 0.0s

Rafsan2020Lightest, 131 kB

bokaifShortest, 487B

Toph uses cookies. By continuing you agree to our Cookie Policy.