| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem J
God Created The Integers
Time Limit: 1000ms
Memory Limit: 65536kb Description
“God created the integers, while the rest is the work of man” is a famous remark on mathematics by Kronecker, a famous mathematician. People understand numbers gradually through the process of solving equations. A very long time ago, people only know the integers Z. In order to let the equation 2x+1=0 has a solution, they introduce the notion of rational numbers Q. Later, man find that there is quite a lot situation requiring the solvability of equations x^2=0, which leads to the emergence of real numbers R. Finally, people import the concept of complex numbers C to make any polynomial has a zero point.Number theory is a centuries-old subject focusing its attention on the theory of integers. There are many beautiful theorems and methods in number theory. As with everything else, so with the number theory: beauty can be perceived, but not explained. In this problem, we will try to solve an interesting one. Mathematicians also try to solve equations in number theory, but here they do it in a different way. For example, they find quadratic equations x^a ≡0(mod b) is of special importance. As you can see, the operation related here is taken in the modular form. If you are familiar with number theory, you will find that we only need to consider the situation where b is a prime through the famous Chinese Remainder Theorem. Now, let us consider the equation x^2≡ t(mod p) where p is a prime. Unfortunately, not any t can guarantee the existence of b satisfying b^2≡t(mod p). It is important to find the condition of t guaranteeing the solvability. But as you know, this problem is a little difficult and thus let us try to solve a little easier problem related. Let p be a prime and p 1(mod 4). You are asked to calculate：  where [a] denotes the largest integer not larger than a. Since sp can be quite large and as a lover of number theory, you are required to calculate its reverse with respect to p, namely, the number rp satisfying 0 < rp < p and rpsp≡1(mod p). Input
The first line contains a number T ≤ 200, which indicates the number of test case.Then in follows T lines, each line is a prime number p. 10<p< 4 *10^8, p≡1( mod 4 ). Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is rp.
Sample Input
2 17 29 Sample Output
Case #1: 15 Case #2: 28 Source
Huicpc302@Zealor
|