TopCoder

柊 四千
あぅあぅ~

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

69.2% (9/13)

Tags

Description

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

為了前往外太空解救妁艷, 妤嬌決定前往歐洲尋找最先進的航太科技. 這個國家是位在白俄羅斯和波蘭的邊境的一個小王國。

啵啵啪啪王國, 一個世襲君主國家, 國民血統為純正的 1/2 白俄羅斯+1/2 波蘭 的完美比例組成. 國民擁有驚人的平均514的智商, 能發展

出遠遠超越SERN的核物裡和遠遠超越 地球聯合,吉翁,紮夫特的航太科技,並不意外。

身為潮能力者, LEVEL-5, 像是穿越電腦螢幕網路王國傳送(Network Transfer to Realms)這種事情妤嬌當然做過很多次。

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

「姊姊, 我也... 我也快不行了~~~」

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

妤嬌說「沒辦法, 妳們兩個一起來吧!」

「嗚!! 兩邊!? 兩邊一起絕對不行的!!」兩位美少女同聲道.

(十分鐘過後)

「啊~ 妤嬌~~」

「妤嬌葛格~~ 啊~~」

三人都因為使力而身體微微泛紅, 身上沾著彼此的汗珠.

「要去了!!!!!!」 妤嬌喘著氣大喊.

「在裡面!?!?!?!?」

「妤嬌!!!!~~~~~~~~~」

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

“要產品序號!?”

點開遊戲後才發現事情不妙!
在妤嬌的記憶中, 序號是由下列方法所生成的:
給定質數 p, 和正整數 b, c, n, 定義序列
a0 = 1
ai *(ai+1 -c)=b (for i=0,1,...) 序號為最小的正整數m, 使得p|m*an -1 由於妤嬌是個天才, 你只需要幫他驗算就可以了, 輸出序號 mod q.

Input Format

第一行有四個正整數 b, c, n, p, q. 其中 p, q 為質數, 意義如上文所述.
對於 30%的測資 n, p ≤ 1,000
對於 60%的測資 n, p ≤ 1,000,000
對於 100%的測資 b, c, n, p, q ≤ 2,000,000,000 且 gcd(b, c) = 1

Output Format

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

Sample Input 1

3 4 2 5 7

Sample Output 1

0

Hints

a0 = 1
a1 = 7
a2 = 31/7
故m=7
m mod 7 = 0

Problem Source

原TIOJ1790 / problem setter: willyliu

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10