Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Quadratic Residues
Time Limit: 1000MSMemory Limit: 30000K
Total Submissions: 1979Accepted: 673


In 1801, Carl Friedrich Gauss (1777-1855) published his "Disquisitiones Arithmeticae", which basically created modern number theory and is still being sold today. One of the many topics treated in his book was the problem of quadratic residues.
Consider a prime number p and an integer a !≡ 0 (mod p). Then a is called a quadratic residue mod p if there is an integer x such that
x2 ≡ a (mod p),
and a quadratic non residue otherwise. Lagrange (1752-1833) introduced the following notation, called the "Legendre symbol":

For the calculation of these symbol there are the following rules, valid only for distinct odd prime numbers p, q and integers a, b not divisible by p:

The statements 1. to 3. are obvious from the definition, 4. is called the Completion Theorem, and 5. is the famous Law of Quadratic Reciprocity for which Gauss himself gave no less than six different proofs in the "Disquisitiones Arithmeticae". Knowing these facts, one can calculate all possible Legendre symbols as in the following example:


The first line contains the number of scenarios.
For each scenario, there is one line containing the integers a and p separated by a single blank, where 2 < p < 109 is an odd prime, and a satisfies both a !≡ 0 (mod p) and |a| <= 109.


Start the output for every scenario with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing (a/p), followed by a blank line.

Sample Input

29 79
2 29
1 3

Sample Output

Scenario #1:

Scenario #2:

Scenario #3:


TUD Programming Contest 2003, Darmstadt, Germany

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator