hdu3589

maksyuki 发表于 oj 分类,标签:
0

Jacobi symbol

Problem Description

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 introduced the following notation, called the Legendre symbol, L (a,p):

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 Jacobi symbol, J (a, n) ,is a generalization of the Legendre symbol ,L (a, p).It defines as :
1.  J (a, n) is only defined when n is an odd.
2.  J (0, n) = 0.
3.  If n is a prime number, J (a, n) = L(a, n).
4.  If n is not a prime number, J (a, n) = J (a, p1) *J (a, p2)…* J (a, pm), p1…pm is the prime factor of n.

Input

Two integer a and n, 2 < a< =106,2 < n < =106,n is an odd number.

Output

Output J (a,n)

Sample Input

3 5

3 9

3 13

Sample Output

-1

0

1

Author

alpc41

 

题目类型:平方剩余

算法分析:这里考察了平方剩余的雅克比标号,按照题目的描述计算即可。该题本质上就是将一个数进行素因子分解,然后对于每个素因子都用欧拉判定条件来计算值,若p | a,则(a, p) = 0。若(a, p) = 1,则答案直接乘上1,否则答案直接乘上-1。注意这里的素因子是整数n所有的素因子(含重复的)!!!