SPOJ.com - Problem LEGRENDS

LEGRENDS - Legendre symbol

no tags

Given 2 integers a and p (1 ≤ a, p ≤ 1000000, p is prime) calculate the Legendre symbol (a/p).

Input

In the first line the number of test cases t < 100000. Then t lines with the 2 integers a and p.

Output

t lines with the Legendre symbol (a/p).

Example

Input:
4
2 7
5 7
14 7
3 2

Output:
1
-1
0
1

Submit solution!

hide comments

< Previous 1 2 3 Next >

	Michael T: 2011-07-23 10:27:23 @HWK: It definitely does. Problem is en.wiki states: "let p be an odd prime number" in definition. So maybe you should have used mathworld instead. Where p-odd-prime is only an "if". Last edit: 2011-07-21 10:15:58
	HWK: 2011-07-23 10:27:23 For the participants which understand German: http://de.wikipedia.org/wiki/Legendre-Symbol Here you find a definition for L(a,2). But I thought that the majority don't understand German so I inserted the link to the English wikipedia page. But anyway: In my problem I ask for the 'Legendre symbol' for p is prime but not p is odd. So also the answer for p=2 is expected. Sorry for the trouble but I think it makes the problem slightly more interesting.
	Hagen von Eitzen: 2011-07-23 10:27:23 In the wikipedia article the problem links to, the Legendre symbol is explicitly not defined for p=2. Hence I don't see why there is so much discussion about "the even prime" here becasue any input case with p=2 would be illegal/the output undefined.
	Noszály Csaba: 2011-07-23 10:27:23 i don't know that my solution fails only on p=2 or not, but i am curious what is the definition of (a/2), considering that -1=1(mod 2).
	HWK: 2011-07-23 10:27:23 @anubhav gupta: Rethink your calculation for the even prime. ;-) Last edit: 2011-07-14 19:58:35
	anubhav gupta: 2011-07-23 10:27:23 @HWK for even prime if have calculated the value but still wa
	HWK: 2011-07-23 10:27:23 @anubhav gupta: Think of an even prime. ;-)
	anubhav gupta: 2011-07-23 10:27:23 @HWK can u check soution id 5377398. its giving wa. can u tel me why??
	shinoda: 2011-07-23 10:27:23 @HWK why i'm getting WA?? i've tested some test cases and is working fine... can you see my last submissions? AC! ;) Last edit: 2011-07-13 23:57:19
	HWK: 2011-07-23 10:27:23 @Problem Solver: Thank you. :-) Would you try to beat 0.12 secs? ;-)

Submit solution!

Added by:	HWK
Date:	2011-07-11
Time limit:	3.049s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64