“any sources of information” refers only to code written by the contestant before the contest, such as GitHub templates or old Codeforces submissions.

This does not permit viewing others’ code, searching for solutions online, or discussing the problems. Contestants may not read blogs or algorithm explanations on websites such as Codeforces or CP-Algorithms.

So apparently you can only view codes written by yourself. Not sure how they're going to police it though

I thought about keeping n constant: If you do not change it, and only alternate with the second range, it will be log(n)*(n^(1/2)) + sqrt(1e9) + sqrt(1e9)/2... since 1, 2... sqrt(n) doesn't decrease. However, to make this work, you can do one iteration on 1, 2, sqrt(n), then one iteration on sqrt(n), 2*sqrt(n).. n This will be as such: 1st: sqrt(n) + sqrt(n)/2 2nd: sqrt(n)/2 + sqrt(n)/2 3rd: sqrt(n)/2 + sqrt(n)/4 4th: sqrt(n)/4 + sqrt(n)/4 ... Which sums up to be around 158000 for 1e9. And that nets you 50pts on the 3rd subtask. You can optimize the 1st iteration, since it will always trigger for l=1e9/2 r = 1e9 (for bs on the left sequence), you can make the first one take sqrt(n) queries only, instead of 3/2sqrt(n) queries. Netting around 55pts. Maybe this kind of logic could be merged to give a better score ?

Ok, I found the AC sol:

We can assume that the mod > 1e9/2

Now, we have number of queries is 2sqrt(1e9/4) + 2sqrt(1e9/8) + 2sqrt(1e9/16) + 2sqrt(1e9/32)... = 108000 queries (we already reduced it to [1e9/2, 1e9] so it takes 2sqrt(1e9/2/(2**i)) for the ith iteration (0 indexed)) We know that if x is the modulo, then a*x will also cause collisions as if it was the modulo. (a being a positive integer)

And so, what we can try to do, is to try to remove a prime factor one by one from our answer.

Let's say we got answer x

We will query [x/p+1, 1] to check if the actual answer was smaller than x.

if it returns 1 collision, then x:=x/p

We repeat this until we don't get any collisions with all primes.

This should stay under 1.1e5.

I first thought about cheaply verifying if x <= n for some x. If we can do that we can binary search on n.

I noticed that the collision thingy only outputs positive integers if there are two numbers in its input whose difference is divisible by n. So if I were to somehow input a short list of numbers such that all differences in 1...n were present, we can check if x <= n definitively just by checking if anything collided. A simple construction for n = 81 is as follows:

1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 81 82

I think this example will show the idea pretty well but the idea is you can use first O(B) numbers to create first B-1 diferences and O(N/B) numbers to get the rest. selecting B~O(sqrt N) yields around 43 pts. Then you basically optimise empirically, I got 78 pts for a long time but managed to optimise to 83 pts with a few math observations