| 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
|
||||||
|
2022-07-28 06:26:51 Mitch Schwartz
@Francky: It's great to see you here too. Email sent! |
||||||
|
2022-07-27 19:04:15 Francky
@Mitch, could you email me ? Happy to see you again here ;-) |
||||||
|
2022-07-22 13:32:38 Mitch Schwartz
In my view there is very little cause for confusion here. The usual definition for Legendre symbol (not the one using Euler's criterion, but the one that lists 3 cases) can be applied to p = 2 without any ambiguity or difficulty, provided you know what a quadratic residue is. If you happen to have some familiarity with the territory (quadratic reciprocity, Jacobi symbol), then you may get a good sense of why p = 2 is typically excluded from the definition, but for a programming exercise it seems good to encourage solvers to think about this case rather than, say, applying a formula blindly. Incidentally, the Kronecker symbol (a/n) uses a different definition for n = 2. Last edit: 2022-07-22 21:03:44 |
||||||
|
2022-07-22 03:54:57 vas14
Not sure why the author thinks including cases for p = 2 is "interesting." It takes more time to google the appropriate definition of quadratic residue for p = 2 than to actually solve this problem. To save people time, the answer to this problem for p = 2 will be 0 for even values of a and 1 otherwise. |
||||||
|
2012-11-16 06:44:43 Pranjali Pratik
@HWK : Can you take a look at solution 8062878? I can't place what the error may be. |
||||||
|
2012-07-07 17:10:34 Ajey Golsangi
The ans for (4,2) is 0 |
||||||
|
2012-06-15 18:46:48 praveen123
If a function is not defined for some value , then how can you ask us to predict its value at that point. For prime p = 2 ,,, even definitions on wikipedia do not give one answer , if a is divisible by 2 ,, then what should be answer ,,, it can be 0 and 1 as well. So please properly define your function . |
||||||
|
2011-07-23 10:27:23 HWK
@blashyrkh: I don't believe that the mathworld definition is really better then the wiki one but I changed it as desired. Last edit: 2011-07-22 07:30:17 |
||||||
|
2011-07-23 10:27:23 blashyrkh
@HWK: Change it in a different way, please. Give a link to mathworld definition and remove a caution. Let the problem be more interesting. |
||||||
|
2011-07-23 10:27:23 HWK
Changed problem description. |
||||||
RSS