1023 . Brute-force Algorithm
Description
Professor Brute is not good at algorithm design. Once he was asked to solve
a path finding problem. He worked on it for several days and finally came up with
the following algorithm:
Any fool but Brute knows that the function “funny” will be called too many
times. Brute wants to investigate the number of times the function will be called,
but he is too lazy to do it.
Now your task is to calculate how many times the function “funny” will be called,
for the given a, b and n. Because the answer may be too large, you should output
the answer module by P.
Input Format
There are a lot of test cases. The first line of the input contains an integer
T, meaning the number of the test cases.
For each test cases, there are four integers a, b, P and n in a single line.
You can assume that 1≤n≤1000000000, 1≤P≤1000000, 0≤a, b<1000000.
Output Format
For each test case, output the answer with case number in a single line.
Sample Input 1
3 3 4 10 3 4 5 13 5 3 2 19 100
Sample Output 1
Case #1: 2 Case #2: 11 Case #3: 12
Hints
Problem Source
Migrated from old NTUJ.
2009Shanghai
Subtasks
| No. | Testdata Range | Score |
|---|