d022: 習題 Q-2-13. 無理數的快速冪 (108 高中全國賽, simplifed)
Tags : Binary Exponentiation
Accepted rate : 6人/7人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-01-30 08:28

Content

若 $s + t\sqrt{2} = (x + y\sqrt{2})^n$,其中 x, y, s, t 均為正整數

輸入 $x$, $y$ 與 $n$

請計算並輸出$s$與$t$除以$p$的餘數

$p=10^9+9$且$x,y,n < p$

Input

一行含三個正整數,依序為$x$, $y$與$n$,以空格隔開。

Output

$s$ 與 $t$,中間空一格。

Sample Input
2 3 2
Sample Output
22 12
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
Binary Exponentiation
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


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