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
hide comments
|
Mitch Schwartz:
2022-07-28 06:26:51
@Francky: It's great to see you here too. Email sent! |
|
Francky:
2022-07-27 19:04:15
@Mitch, could you email me ? Happy to see you again here ;-) |
|
|
Mitch Schwartz:
2022-07-22 13:32:38
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 |
|
vas14:
2022-07-22 03:54:57
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. |
|
Pranjali Pratik:
2012-11-16 06:44:43
@HWK : Can you take a look at solution 8062878? I can't place what the error may be. |
|
Ajey Golsangi:
2012-07-07 17:10:34
The ans for (4,2) is 0 |
|
praveen123:
2012-06-15 18:46:48
If a function is not defined for some value , then how can you ask us to predict its value at that point.
|
|
HWK:
2011-07-23 10:27:23
@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 |
|
blashyrkh:
2011-07-23 10:27:23
@HWK: Change it in a different way, please. Give a link to mathworld definition and remove a caution. Let the problem be more interesting. |
|
|
HWK:
2011-07-23 10:27:23
Changed problem description. |
| 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 |
RSS