|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).
In the first line the number of test cases t<100. Then t lines with the 2 integers a and p.
t lines with the Legendre symbol (a/p).
3 2 Output: 1
|Cluster:||Cube (Intel G860)|
|Languages:||All except: SCM qobi|
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
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.