In the game BioHazard 4, the president's daughter has been abducted by some crazy villagers. Leon S. Kennedy, the secret agent of White House, goes to rescue her. He keeps in contact with Hunnigan, the president's secretary.
But the time in their contact log has been encrypted, using the following method:
Count the number of seconds from 2000.01.01 00:00:00 to that time, assume this number is x. Then calculate xq
, modulo it by a prime number p. The remainder a
is the encrypted number.
Your task is to help Leon write a program to decrypt the contact log, and tell
him all the possible original time.
1. Remember that if the year can be divided evenly by 4 but can't be divided
evenly by 100, or it can be divided evenly by 400, this year is a leap year. The
February of a leap year has 29 days, while the February of other years has 28
days.
2. In this problem, if the year modulo 10 is 5 or 8, at the end of this year,
there is one “leap second”, i.e., the second after 2005.12.31 23:59:59 is
2005.12.31 23:59:60, and after that second, it's 2006.01.01 00:00:00.
You may assume that from 2000.01.01 00:00:00 till that time, less than p seconds
have passed.
There are multiple test cases.
The first line of the input contains an integer T, meaning the number of the
test cases.
For each test case, a single line of three integers: p, q, and a. (2<p≤1000000007, 1<q≤10, 0≤a<p, p is always a prime.)
The time. If there are multiple solutions, you must output all possible
solutions in chronological order.
If the solution doesn't exist, output Transmission error instead.
See the sample output for further details.
2 3 2 1 3 2 2
Case #1: 2000.01.01 00:00:01 2000.01.01 00:00:02 Case #2: Transmission error
Migrated from old NTUJ.
2009Shanghai
| No. | Testdata Range | Score |
|---|