题目描述
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.
输入
Two integer a and n, 2 < a< =1000000，2 < n < =1000000，n is an odd number.