https://www.acmicpc.net/problem/24711


seed의 값을 알아내면 그 뒤로는 비교의 결과값을 정확히 알 수 있으므로 이분탐색 문제가 되고 60 쿼리에 풀린다.
그러므로 40 쿼리를 써서 난수 값을 바탕으로 거꾸로 seed를 알아내는 게 핵심이다.

seed를 알아내는 동안은 난수 값을 정확히 알아내기 위해서 똑같은 x 값에 대해서 반복해서 쿼리를 한다.
x = 1을 쓴다고 하면 비교의 결과는 y = 1일 때 1 아니면 y > 1일 때 2만 나오게 되는데, 둘 중의 한 상황에 대해서 모순을 찾기 전까진 두 상황을 모두 고려하고 있어야 하므로 각각의 경우에 대해 seed를 구한다.

문제의 난수 알고리즘을 보면 seed에 n을 곱한 다음 P로 나눈 나머지를 구하고 다시 n으로 나눈 나머지를 구하고 있다.
만약 이때 seed * n이 P보다 작아서 P로 나머지를 구하는 연산이 아무런 영향을 안 준다면 result가 0이 나온다.
이런 성질로부터 seed의 정확한 값보다는 seed의 대략적인 크기가 더 중요할 것 같다.
실제로 q를 seed * n을 P로 나눈 몫이라 했을 때 (즉, q = floor(seed * n / P)) result = (seed * n - q * P) % n = (n - q) * P % n이 된다.
문제의 범위에서 n과 P는 서로소이므로 난수값을 알면 q 값을 알아낼 수 있다.

H를 i번 호출한 뒤의 seed 값을 seed_i이라 하고, (i >= 0)
i번째 난수값으로부터 구한 q 값을 q_i라 하자. (i >= 1) 그러면 다음이 성립한다.

seed_0 * n = seed_1 + P * q_1
seed_0 * n^2 = seed_1 * n + P * n * q_1 = seed_2 + P * (q_2 + n * q_1)
...
seed_0 * n^k = seed_k + P * (q_k + ... + n^(k-1) q_1)

이때 양 변의 값이 n^k의 배수가 되어야 하는데, k개 쿼리를 날리고 나서는 모든 q 값이 정해지므로 우변에서 모르는 값은 seed_k밖에 없다.
0 <= seed_k < P이므로 n^k >= P인 k에 대해서 seed_k로 가능한 값은 1개 이하이다.
3^38 > 10^18이므로 38쿼리면 각 가정한 상황에 대해서 seed를 구할 수 있다.
여기서 가능한 값이 안 나오면 가정했던 비교의 결과값이 틀렸던 거니까 둘 중 한 상황을 폐기하면 되는데, 두 상황 모두 가능한 seed 값이 남아있을 수도 있다.

y = 1인 상황과 y > 1인 상황이 둘 다 남아있다고 하자.
그러면, 만약에 쿼리를 좀 더 돌려서 실제로는 y = 1이라는 사실을 알게 되면 답을 알아낸 거니까 별 문제가 없는데
중간에 y > 1이라는 사실을 알아내면 이분탐색에 쓸 쿼리가 모자라질 수가 있다.
따라서 둘 다 남아있으면 일단은 y > 1 기준으로 이분탐색을 돌리면서, 각 상황이 여전히 가능한지를 체크해야 한다. 이 구현은 알아서 하자.

이 풀이는 두 상황이 모두 100쿼리동안 모순이 안 나오는 경우 틀리게 된다. 아마 3^100이 seed 값의 가능한 범위보다 많이 커서 찾기 쉽진 않을텐데 없는지는 잘 모르겠다.