2327 . 堆雪人
TopCoder
Tags
Description
阿格尼與露娜除了烤肉以外最喜歡的就是玩雪了，今天他們要來堆雪人。
只是堆出來的雪人不知道為什麼野獸化變成了長毛的怪獸雪人，於是露娜對阿格尼說：「對他使用炎拳吧。」
話說回來阿格尼與露娜總共有 $a^ x$ 公斤的雪，一個雪人可以用 $b^ y$ 公斤的雪堆出來。
阿格尼與露娜想知道他們最多可以堆出幾個雪人，假設可以堆出 $A$ 個，並且堆完後會剩下 $B$ 公斤的雪，請你求出 $A,B$。
因為 $A,B$ 可能會很大，所以請輸出 $A\text{ mod }N$ 與 $B\text{ mod }M$。
Input Format
輸入一行，有 $6$ 個正整數，分別是 $a,b,x,y,N,M$。
對於所有測試資料：
- $1\leq a,b,x\leq 10^ 9$
- $2\leq N,M\leq 10^ 9$
- $1\leq y\leq 1000$
Output Format
輸出 $A\text{ mod }N$ 與 $B\text{ mod }M$。
Sample Input 1
3 5 10 4 28 35
Sample Output 1
10 19
Sample Input 2
42 1 888 999 13579 12345
Sample Output 2
9498 0
Sample Input 3
48763 1 111111111 154 4949 1000
Sample Output 3
2199 0
Sample Input 4
10 2320 999998888 1 14107 1910
Sample Output 4
13943 320
Hints
在範例測資一：$a^ x=3^ {10}=59049,b^ y=5^ 4=625$，
可算出 $A=94,B=299$，$A\text{ mod }N=94\text{ mod }28=10$，$B\text{ mod }M=299\text{ mod }35=19$。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~3 | 範例測資 | 0 |
| 2 | 1, 4~13 | $x\leq 10^ 5,b=1$ | 8 |
| 3 | 1~2, 4~20 | $b=1$ | 11 |
| 4 | 3, 21~32 | $y=1,b<N,N$ 是質數 | 18 |
| 5 | 3, 21~48 | $y=1$ | 21 |
| 6 | 0~96 | 無其他限制 | 42 |