| Submit | All submissions | Best solutions | Back to list |
LEGRENDS - Legendre symbol |
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
| 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 |
hide comments
|
||||||
|
2011-07-23 10:27:23 Michael T
@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 |
||||||
|
2011-07-23 10:27:23 HWK
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. |
||||||
|
2011-07-23 10:27:23 Hagen von Eitzen
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. |
||||||
|
2011-07-23 10:27:23 Noszály Csaba
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). |
||||||
|
2011-07-23 10:27:23 HWK
@anubhav gupta: Rethink your calculation for the even prime. ;-) Last edit: 2011-07-14 19:58:35 |
||||||
|
2011-07-23 10:27:23 anubhav gupta
@HWK for even prime if have calculated the value but still wa |
||||||
|
2011-07-23 10:27:23 HWK
@anubhav gupta: Think of an even prime. ;-) |
||||||
|
2011-07-23 10:27:23 anubhav gupta
@HWK can u check soution id 5377398. its giving wa. can u tel me why?? |
||||||
|
2011-07-23 10:27:23 shinoda
@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 |
||||||
|
2011-07-23 10:27:23 HWK
@Problem Solver: Thank you. :-) Would you try to beat 0.12 secs? ;-) |
||||||
RSS