| Submit | All submissions | Best solutions | Back to list |
NSQUARE - NSquare Sum ( Easy ) |
Given two integers N (N <= 1018) and a prime number P (1 < P < 1018), find the lowest number x such that there are not N integers greater or equal to 0 whose sum of squares is equal to x.
N = 2, P = 2 x = 3 mod 2 = 1 0 = 02 + 02 1 = 12 + 02 2 = 12 + 12 4 = 22 + 02
Input
The two integers N (1 <= N <= 1018) and a prime number P (1 < P < 1018). You have to print the answer modulo P.
Output
You have to print an integer x mod P (-1 < x < 1018 + 1) that satisfies the problem. If there's no number x, print "Impossible".
Example
Input: 1 3 Output: 2
Input: 13 7 Output: Impossible
| Added by: | Mateus Dantas [ UFCG ] |
| Date: | 2012-09-30 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
| Resource: | Rafael Perrela |
hide comments
|
|||||
|
2018-07-15 20:09:47
trickily easy :p |
|||||
|
2016-03-12 17:58:26 Umesh Malhotra
First solve it by filling 100 by 100 2-d matrix,then you will figure out that its a very easy problem |
|||||
|
2016-02-04 14:57:31 Devashish Mathur
Haha.. easy problem :) |
|||||
|
2012-10-03 11:55:38 Francky
I suspect it is possible that n and p are sometimes on separate lines on some test files ! Python users should be careful about that. If yes, it should be corrected. ;-) |
|||||
|
2012-09-30 23:28:41 Mateus Dantas [ UFCG ]
Correct now. Thank you! |
|||||
|
2012-09-30 23:28:41 mehmetin
I solved the problem, but ^1's should be ^2's in the (N=2,P=2) example case. It says sum of squares in the description. Last edit: 2012-09-30 17:39:11 |
|||||
|
2012-09-30 23:28:41 Mateus Dantas [ UFCG ]
This problem is a big tricky, hehe. |
|||||
|
2012-09-30 23:28:41 Francky
Edit : My code failed only for 1 2 ;-), now AC. Last edit: 2012-09-30 13:43:05 |
|||||
|
2012-09-30 23:28:41 :D
The problem seems to be "that" easy. Only thing you have to remember, is that you are not looking for x in <0;P), but in <0;inf). That, however, is properly described. |
|||||
|
2012-09-30 23:28:41 (Tjandra Satria Gunawan)(曾毅昆)
be careful, this problem is a bit tricky. |
|||||
RSS