problem is from NEERC 2011 named "gcd guessing game"↵
↵
↵
you are given number N which is less than or equal to 10000. (1 <= N <= 10000)↵
number X is hidden. (1 <= X <= N)↵
for each query, you can choose any number Y from 1 to N and get gcd(X,Y).↵
at least how many query you need to determine number X?↵
↵
↵
↵
solution for this problem is to gather all prime numbers from 1 to N and group them so that product of each group does not exceed N. number of group is our answer. let's say this number G.↵
↵
↵
my question is ↵
with strategy above, we can only determine which prime factor does X have.↵
for example if X is (2^3) * (3^5) , we can say X is multiple of 6 but can't tell how many 2 and 3 does X have. so we need additional query to determine it. so there can be a number we can't certain with G queries. how can we prove there are no such numbers?↵
↵
↵
sorry for my poor english.
↵
↵
you are given number N which is less than or equal to 10000. (1 <= N <= 10000)↵
number X is hidden. (1 <= X <= N)↵
for each query, you can choose any number Y from 1 to N and get gcd(X,Y).↵
at least how many query you need to determine number X?↵
↵
↵
↵
solution for this problem is to gather all prime numbers from 1 to N and group them so that product of each group does not exceed N. number of group is our answer. let's say this number G.↵
↵
↵
my question is ↵
with strategy above, we can only determine which prime factor does X have.↵
for example if X is (2^3) * (3^5) , we can say X is multiple of 6 but can't tell how many 2 and 3 does X have. so we need additional query to determine it. so there can be a number we can't certain with G queries. how can we prove there are no such numbers?↵
↵
↵
sorry for my poor english.
