Guessing with GCD
National Olympiad — National round (2022 season)
Submission name: gcd.cpp
Problem summary
Recover a hidden integer X in [0,MAX_X) using query(a,b)=gcd(X+a,b). This is a scored interactive task: fewer average queries earn more points.
Source clarification. The PDF lists MAX_X=0 although no X satisfies 0≤X<MAX_X in that case. The function makes no query and returns 0 for that empty-domain parameter; no hidden-value correctness claim is meaningful there.
Input
The grader calls ull play(ull MAX_X); use ull query(ull a, ull b) from gcd.h.
Output
Return X. Do not read or print anything in the submitted function.
Constraints
The meaningful hidden-number domain is 1 ≤ MAX_X ≤ 10^9; 0 ≤ a < 2*MAX_X and 1 ≤ b < 2*MAX_X. Official scored cases use MAX_X=100 and 10^9.
Worked example
An independently prepared example for this explanation.
Input
Local mock: MAX_X=10, X=6.
Output
play(10) returns 6.
Solution analysis
- Recover X from low bits to high bits. Maintain residue r=X modulo p, where p is a power of two. Ask gcd(X+(p−r),2*p). Since X−r is a multiple of p, the answer is either p or 2*p.
- The answer is 2*p exactly when the next bit of X is one; in that case add p to r. Double p and repeat until p≥MAX_X. Then the known residue is the complete hidden number. Every a=p−r lies in [1,p], and every queried modulus satisfies 2*p<2*MAX_X.
- For hidden X=6 and MAX_X=10, the queries are (1,2), (2,4), (2,8), (2,16), returning 1,4,8,8. The recovered residues are 0,2,6,6. This exact method uses at most 30 calls for the largest domain; its score follows the official average-query formula and is not claimed to reach the best average-score target.
Why it works
Initially r=0 is X modulo 1. Write X=r+p*q. The queried sum is p*(q+1), so its gcd with 2*p is 2*p if q is odd and p if q is even. These are precisely the two possibilities for X modulo 2*p, proving the updated residue invariant. At termination 0≤X<MAX_X≤p, so r=X.
Watch out. Use the exact grader interface, not standard input. The guarantee is recovery correctness within valid query bounds, not maximum competition score.
Commented C++17 solution
Grader-linked C++17 module using gcd.h; no main. The example describes a local mock with a chosen hidden X, not standard input/output. Exact recovery uses at most ceil(log2(MAX_X)) calls and does not guarantee maximum score under the average-query scoring rule.
#include"gcd.h"
ull play(ull MAX_X){
ull residue=0;
for(ull power=1;power<MAX_X;power*=2){
// residue is X modulo power; the query reveals the next bit.
ull answer=query(power-residue,2*power);
if(answer==2*power){
residue+=power;
}
}
return residue;
}