Find the Modulus solution codechef

Find the Modulus solution codechef

The jury has a secret number NN, where 1N10181≤N≤1018. You want to know this number, and you are allowed to ask the jury some queries. In each query, you give the jury a number XX where 0X210180≤X≤2⋅1018, and the jury tells you XmodNXmodN.

Please find NN using at most two queries per test case.

Interaction Format

Find the Modulus solution codechef

  • The first line of contains TT – the number of test cases.
  • For each test case, you are allowed to allowed to ask the jury at most two queries. To make a query, output ? X on one line; the jury will return the value of xmodNxmodN to the input for you to read.
    • In the case you exceed the number of queries, the judge will exit with the Wrong Answer verdict.
  • Once you have found the answer, output ! N on one line. This does not count as a query.
    • If you output the wrong value for NN, the judge will exit with the Wrong Answer verdict; if you output the correct value for NN, the judge will silently continues. This means you should start asking queries for the next test case right after outputting the value of NN for the previous test case.

Constraints

Find the Modulus solution codechef

  • 1T1001≤T≤100
  • 1N10181≤N≤1018
  • 0X210180≤X≤2⋅1018

Sample Input 1

Find the Modulus solution codechef

2
5
0
4
5

Sample Output 1

Find the Modulus solution codechef

? 5
? 6
! 6
? 4
? 5
! 39

Explanation

Find the Modulus solution codechef

  • Test case 11: Jury’s secret number is N=6N=6. Your first query is X=5X=5, so the jury returns 5mod6=55mod6=5. Your second query is X=6X=6, so the jury returns 6mod6=06mod6=0. Finally, you output 66 as the final answer, which is the correct answer.
  • Test case 22: Jury’s secret number is N=39N=39. Your first query is X=4X=4, so the jury returns 4mod39=44mod39=4. Your second query is X=5X=5, so the jury returns 5mod39=55mod39=5. Finally, you output 3939 as the final answer, which is the correct answer (but a completely wild guess).

Note that the jury does not output anything other than the answers to the queries, so please start asking queries for the next test case after outputting NN for the previous test case.

Leave a Comment