시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 25 | 5 | 4 | 16.667% |
Master Zhu has a number $n$. He asks you $q$ queries, the $i$-th query is a pair of integers $(x_i, y_i)$. For $i$-th query, Master Zhu would like you to find the smallest non-negative integer $k_i$ such that, for some $p$ which is a prime divisor of $n$, the equivalence $x_i^{k_i} \equiv y_i$ modulo $p$ holds, or to determine that no such $k_i$ exists.
In this problem, we consider that $0^0 = 1$.
The first line of input contains two integers $n$ and $q$ ($1 \le n \le 10^8$, $1 \le q \le 10^5$). Each of the next $q$ lines contains two integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le 10^9$).
For each query, print the answer on a separate line. If you found $k_i$, print it, otherwise print the number $-1$.
175 2 2 1 2 3
0 3