P2485 [SDOI2011] Calculator

2024-08-11 update: Added a new hack.

You are asked to design a calculator to complete the following three tasks: 1. Given $y, z, p$, compute the value of $y^z \bmod p$. 2. Given $y, z, p$, compute the smallest non-negative integer $x$ such that $xy \equiv z \pmod p$. 3. Given $y, z, p$, compute the smallest non-negative integer $x$ such that $y^x \equiv z \pmod p$. Do your best to win the prize!

The input contains multiple test cases. The first line contains two positive integers $T, K$, denoting the number of test cases and the query type, respectively (for all testdata within a single test point, the query type is the same). Each of the following $T$ lines contains three positive integers $y, z, p$, describing one query.

The output contains $T$ lines. For each query, output one line with the answer. For query types $2$ and $3$, if no solution exists, output `Orz, I cannot find x!`.

Test points are divided into three categories. The proportion of each category among all test points is as follows: | $K=$ | Proportion of test points | | :--: | :-----------------------: | | $1$ | $20\%$ | | $2$ | $35\%$ | | $3$ | $45\%$ | All testdata satisfy: $1 \leq y, z, p \leq 10^9$, $p$ is prime, and $1 \leq T \leq 10$. Translated by ChatGPT 5