CRYPTO7 - Cryptography Reloaded (Act II)
Please click here to download a PDF version of the contest problems. The problem is problem D in the PDF.
In the game BioHazard 4, the American 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 times.
- 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.
- 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.
Input
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.)
Output
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.
Sample
Input: 2 3 2 1 3 2 2 Output: Case #1: 2000.01.01 00:00:01 2000.01.01 00:00:02 Case #2: Transmission error
hide comments
Simes:
2023-02-04 15:05:26
I've extracted the problem from the PDF. I hope that's ok? If there are any mistakes or discrepancies, assume the PDF is correct.
|
Added by: | Fudan University Problem Setters |
Date: | 2009-11-01 |
Time limit: | 5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 C99 GOSU NODEJS OBJC PERL6 VB.NET |
Resource: | ACM/ICPC Regional Contest, Shanghai 2009 |