TIOJ 1790 好激烈

Description

「嗚，不可能，這不可能塞得進去!!! 啊~~~」妤嬌姊姊道。

為了前往外太空解救妁艷，妤嬌決定前往歐洲尋找最先進的航太科技。這個國家是位在白俄羅斯和波蘭的邊境的一個小王國。啵啵啪啪王國，一個世襲君主國家，國民血統為純正的 $1/2$ 白俄羅斯 + $1/2$ 波蘭的完美比例組成。國民擁有驚人的平均 $514$ 的智商，能發展出遠遠超越 SERN 的核物裡和遠遠超越地球聯合、吉翁、紮夫特的航太科技，並不意外。身為潮能力者，LEVEL-5，像是穿越電腦螢幕網路王國傳送 (Network Transfer to Realms, NTR) 這種事情妤嬌當然做過很多次。

「啊~ 好激烈，妤嬌，姊姊快不行了~ 在這樣下去姊姊會~~ 姊姊會壞掉~~」
「姊姊，我也…我也快不行了~~~」

由於妤嬌隨身攜帶的 laptop 螢幕太小了，要把人塞進去有點困難。妤嬌研判，照這樣的情況下去，再把兩個人 (妤嬌自己則可以穿越隧道過去) 都傳送過去之前電腦螢幕有可能會壞掉！

妤嬌說：「沒辦法，妳們兩個一起來吧！」
「嗚!! 兩邊!? 兩邊一起絕對不行的!!」兩位美少女同聲道。
(十分鐘過後)
「啊~ 妤嬌~~」
「妤嬌葛格~~ 啊~~」
三人都因為使力而身體微微泛紅，身上沾著彼此的汗珠。
「要去了!!!!!!」妤嬌喘著氣大喊。
「在裡面!?!?!?!?」
「妤嬌!!!!~~~~~~~~~」

周圍閃了幾下白光，費盡工夫，總算把兩人塞進螢幕裡面了。剩下的工作就有開啓「人工少女 3」把電腦中的兩人送到啵啵啪啪王國了。

「要產品序號!?」

點開遊戲後才發現事情不妙！
在妤嬌的記憶中，序號是由下列方法所生成的：
給定質數 $p$ 和正整數 $b, c, n$，定義序列 $$\begin{cases} a_0 = 1,\\ a_i(a_{i+1}-c)=b,&\text{for }i = 0, 1, \ldots \end{cases}$$ 序號為最小的正整數 $m$，使得 $p|ma_n-1$。由於妤嬌是個天才，你只需要幫他驗算就可以了，輸出序號 $\operatorname{mod}q$。

Input Format

第一行有五個正整數 $b, c, n, p, q$，其中 $p, q$ 為質數，意義如上文所述。
對於 $30\%$ 的測資 $n, p \leq 1000$。
對於 $60\%$ 的測資 $n, p \leq 10^6$。
對於 $100\%$ 的測資 $b, c, n, p, q ≤ 2\times 10^9$ 且 $\gcd(b, c) = 1$。

Output Format

輸出一個正整數 $m \operatorname{mod} q$，意義如上文所述。若此正整數 $m$ 不存在，輸出 $-1$。
但是聰明的你知道，puts("-1");並不會拿到任何分數，因為你很想玩人工少女 3。

Sample Input

3 4 2 5 7

Sample Output

0

Solution

設 $a_i = \frac{\alpha_i}{\beta_i}$，其中 $\alpha_i, \beta_i \in \mathbb{Z}_{\geq 1}$ 且 $\gcd(\alpha_i, \beta_i) = 1$。由 $a_i(a_{i+1}-c)=b$，可知 $$\frac{\alpha_{i+1}}{\beta_{i+1}} = \frac{b\beta_i+c\alpha_i}{\alpha_i}.$$ 假定某個 $i$ 滿足 $\gcd(\alpha_i, b) = 1$，則顯然我們有

1. $\gcd(b\beta_i+c\alpha_i, \alpha_i) = \gcd(b\beta_i, \alpha_i) = 1$
2. $\gcd(b\beta_i+c\alpha_i, b) = \gcd(c\alpha_i, b) = 1$

注意這樣一來

1. $\alpha_{i+1} = b\beta_i+c\alpha_i$
2. $\beta_{i+1} = \alpha_i$
3. $\gcd(\alpha_{i+1}, b) = 1$

因為 $\alpha_0 = \beta_0 = 1$ 且 $\gcd(\alpha_0, b) = 1$，我們得到 $$\begin{pmatrix}\alpha_n\\\beta_n\end{pmatrix} = \begin{pmatrix}c&b\\1&0\end{pmatrix}^n\begin{pmatrix}1\\1\end{pmatrix}.$$ 設 $m = \beta_nx$，其中 $x \in \mathbb{Z}_{\geq 1}$。我們希望找到最小的 $x$ 使得 $ma_n = \alpha_nx \equiv 1\ (\operatorname{mod}p)$，而這只要找到 $\alpha_n$ 在 $\mathbb{Z}_p$ 裡的乘法反元素就行了。

我的 code：
https://ideone.com/PIv8N5