| Submit | All submissions | Best solutions | Back to list |
LEGENDRE - 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<100. 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: | 8.909s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: SCM qobi |
hide comments
|
2014-06-30 21:17:56 challenger
Thanks. I'd suggest removing some parts of your code without thinking whether it will work or not. You'll be surprised how many characters can you cut. ;-) |
|
|
2014-06-30 16:53:01 Dominique VAILLANT
@challenger: 71 with Ruby, very impressive! I had almost no hope to shorten my actual (Ruby) code. Thanks! |
|
|
2011-07-21 14:00:11 HWK
Changed problem description for clarification. Edit: Changed again due to a remark at main SPOJ. Last edit: 2011-07-22 07:32:29 |
|
|
2011-07-14 08:06:14 HWK
@hallvabo: Yes, but in few as builtin. I guess your Bash solution is hard to beat even for Nabb. |
|
|
2011-07-13 23:03:55 Hallvard Norheim Bø
@HWK: it exists in other languages too ;) |
|
|
2011-07-13 21:48:55 HWK
@hallvabo: Seems it was too easy. Try to solve http://www.spoj.pl/problems/LEGRENDS/ . My Python solution requires 6.91 secs. ;-) Last edit: 2011-07-13 21:50:53 |
|
|
2011-07-13 21:22:47 HWK
@hallvabo: Great! My best Python solution requires 102 bytes. First I thought to ban the Python function you used. I already regret that I didn't it. :-) So it will be difficult for Perl. Hi, Jander. I need 91 Perl bytes. ;-) Last edit: 2011-07-13 21:35:52 |
|
|
2011-07-13 21:13:54 Hallvard Norheim Bø
Ok, that was logical. Actually it helped me save two bytes :) |
|
|
2011-07-13 20:56:07 HWK
That is the interesting part. p has to be prime not an odd prime. But for 2 Euler's formula doesn't work. Do you understand German? Then look here: http://de.wikipedia.org/wiki/Legendre-Symbol Last edit: 2011-07-13 20:56:31 |
|
|
2011-07-13 20:24:33 Hallvard Norheim Bø
What should the result be when p=2? According to the definitions I have seen, p must be an odd prime. |
RSS