2013
11-10

# POJ 1808 Quadratic Residues [解题报告] Java

Background

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.

3
29 79
2 29
1 3

Scenario #1:
-1

Scenario #2:
-1

Scenario #3:
1


//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{
public static long mod(long a,long b,long c)
{
long ret=1%c;
while(b!=0)
{
if((b&0x1)!=0)
ret=ret*a%c;
a=a*a%c;
b>>=1;
}
return ret;
}
public static void main(String args[]) throws Exception {

int idx=0;
Scanner cin=new Scanner(System.in);
long a,p;
int t;
t=cin.nextInt();
while(t!=0)
{
--t;
a=cin.nextLong();
p=cin.nextLong();
a%=p;
if(a< 0)a+=p;
++idx;
System.out.println("Scenario #"+idx+":");
if(mod(a,(p-1)/2,p)==1)
System.out.println("1");
else
System.out.println("-1");
System.out.println();
}
}
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

3. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识，这句话用《爱屋及乌》描述比较容易理解……