i619: 我看你…完全是不懂喔 - Extreme
Tags : 分治 數學
Accepted rate : 4人/4人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-08-25 15:18

Content

原題

這個男人實在是太狠了,面對五米高的壯漢,輕輕一推竟然就把他推倒在地。

男人名叫老鼠,是一名住在起士國的學生,這天他與兩名好友大壯和小美走在路上,結果不小心撞到同樣也走在路上的黑老大,這時不出意外的話就出意外了,黑老大把老鼠叫住,你絕對想不到他接下來做的事會改變老鼠的一生。

你有見過這樣子的男人嗎?只見老鼠撞到了走在路上的黑老大,黑老大不但沒有生氣,還對老鼠說要帶他去見一個人。老鼠隨著黑老大進入一個陌生的房間,裡頭走出一名男子,男子自稱杰哥,杰哥對著老鼠的第一句話就是:「讓我看看!」老鼠對著杰哥大喊:「不要!」就把五米高的杰哥推倒在地上了,這時 FBL 衝了進來,把杰哥和黑老大抓住,並把老鼠帶回去審訊。

你有見過這麼奇葩的審問方式嗎?警官大白面對老鼠,拿出一張字條,上面寫著 $1+x+ x^2 + \dots + x^n\ (\bmod m)$,給你 $x, n, m$ 請你算出這條算式的結果。老鼠人狠話不多,一下就算出來了。

Input

第一行有一個正整數 $t$,代表測資筆數。

接下來 $t$ 行,每行有三個正整數 $x, n, m$,代表要請你算出 $1+x+ x^2 + \dots + x^n\ (\bmod m)$,注意 $m$ 不一定是質數。

  • $1 \leq t \leq 10^4$
  • $1 \leq x < m \leq 2 \times 10^9$
  • $1 \leq n \leq 10^{18}$
Output

每行輸出一個數字代表答案。

Sample Input #1
20
1 2 9
8 3 15
1 10 7
2 5 9
5 7 12
6 2 11
1 2 3
3 6 11
1 2 9
5 6 8
8 2 14
1 7 19
5 3 9
6 1 17
4 5 10
1 3 10
8 5 14
2 3 7
1 7 14
9 3 10
Sample Output #1
3
0
4
0
0
10
0
4
3
3
3
8
3
7
5
4
13
1
8
0
Sample Input #2
10
63393781 232566050564766600 93988029
1675520574 367831850847334790 1826703617
1203185979 155949594264662167 1839823831
508094495 513610870612124939 1165310307
585614964 406627357083407581 1000205012
56566560 270964555429459736 925891585
696166569 243794914036887494 924224993
55337810 552163374965210541 1707235562
258393868 817455669382612254 705371932
196361199 109315776933533256 404994462
Sample Output #2
36115792
298737936
854405521
603305388
585049321
583121681
833911828
6434205
18117593
52644859
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 2.0s , <1M
Hint :

$100\%:無特別限制$

Tags:
分治 數學
出處:
[管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」