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. minimum 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.
Auto comment: topic has been updated by p_321052 (previous revision, new revision, compare).
Auto comment: topic has been updated by p_321052 (previous revision, new revision, compare).
I think the algorithm almost works. Maybe after finding the prime you just need query $$$p^k \leq N$$$ for each prime factor $$$p$$$ of the number $$$X$$$ and $$$k$$$ is maximized to find the exponent.
Idk maybe the solution is incomplete.
The idea is to eliminate primes such that $$$X$$$ is not divisible by them. For example, if you make a query with $$$Y = 6$$$ and get a response $$$gcd(X, Y) = 2$$$, then you can eliminate all numbers divisible by 3 (otherwise the $$$gcd$$$ would be equal to $$$6$$$). In the end there will only remain divisors of $$$X$$$, so the largest remaining number is the answer.
But how can we distinguish 2 and 16? We need one more query. What am I misunderstanding?
Okay, I didn't mention the most important part: if we determine that $$$X$$$ is divisible by 2 (for example), than we can ignore all primes larger than $$$\lceil X/2 \rceil$$$ (we know that there is at least one such prime because of Bertrand's postulate) and replace a query of any such prime with a query of largest power of $$$2$$$ not larger than $$$N$$$. I assume (maybe we need to check it by bruteforce) that for all possible outcomes there will be enough large primes to check all required powers.
There are at least one prime between n and 2*n so we can also eliminate other groups too.
that was the key Thank you so much.
Every prime > sqrt(N) appears at most once in a group (this is also a main idea of the solution). Take groups in order of minimum value in a group. Then, by the point that you've queried groups that have some prime <= sqrt(N), you've done O(sqrt(N)/logN) queries. There are waaaaay more big primes than that and in fact waaay more primes > N / 2, these primes having to appear in a group by themselves. So if you've found some prime <= sqrt(N), you can use the queries you would've used for those big primes in order to find the exponent of each individual prime.
This can only fail for small values, so to complete the proof you just need to find a point C such that if N >= C it never fails and bruteforce for small C. Since N is small in this problem you can actually simply bruteforce this strategy for every possible N.