SPOJ.com - Problem ALMISPY

ALMISPY - Almost-isosceles Pythagorean triple (easy)

no tags

(3, 4, 5) is the smallest almost-isosceles Pythagorean triple, as 4 - 3 = 1.
Let S = { (a, a+1, c) | a² + (a+1)² = c² with a and c positive integers}.
One can prove that the set S of almost-isosceles Pythagorean triples is infinite.
There is an obvious total order on this set.

Input

The first line of input contains an integer T, the number of test cases.
On each of the next T lines, your are given two integers n and m.

Output

For each test case, you have to find the nth triple (a, a+1, c) in the ordered set S, and print a and c. As the answer could not fit in a 64-bit container, simply output your answer modulo m.

Example

Input:
3
1 10
2 123
4 289

Output:
3 5
20 29
118 118

Constraints

0 < T < 10^4
0 < n < 10^18
1 < m < 10^9

For your information, my 500B-python3 code get AC in 1.61s with 12MB of memory print.
In Python2.7 : (2.49s, 4.0MB), in Python2+psyco (2.04s, 36MB).
My 1kB C code ran in (0.04s, 1.6MB), and time limit is ×125 this one.
Have fun ;-)
(edit) With wisfaq observation, all my best timings are divided by exactly two!!!
(Edit 2017-02-11, new TL with new compiler. TL 1.11s, in the third (0.37s) my Python3 code ends.)

Submit solution!

hide comments

< Previous 1 2 Next >

	David: 2020-03-31 22:29:46 Awesome problem. Intensive investigations to finally get the solution. =(Francky)=> Many thanks for your appreciation ;-) Last edit: 2020-04-01 13:37:18
	[Lakshman]: 2013-07-24 15:23:48 Please help What is the answer for 1000000000000000000 1000000000 is it §§§§§§§§§. --(edit ans, francky)--> No other cases are provided. Good luck. (Lakshman)-->But can you please tell me where My code fails? --ans(francky)--> You still have negative output for small moduli. Still WA.. I have checked more than 100 random test cases But Still WA. --ans--> Check again for small moduli, say under 6. Your results aren't negative now, but wrong. Thanks Francky got it. Last edit: 2014-02-23 15:33:35
	[Lakshman]: 2013-07-18 19:10:13 @francky Can you please tell me why getting WA, I think my approach is correct. Please help getting WA again and again, Initially I was getting negative value for large input but now I have fixed that. Last edit: 2013-07-19 07:38:13
	Orchid: 2013-06-24 05:57:45 9539091- any hint??checked smaller moduli also..
	SWOOSH!!!: 2013-06-24 05:56:15 Will a always be less than c for any mod? --ans--> Obviously not. For example (3, 4, 5) and mod 5. 3mod5 and 5mod5. Comparison within moduli is a nonsense. Last edit: 2013-06-24 09:26:07
	tuhin: 2013-06-24 04:45:30 AC :) Last edit: 2013-07-04 04:33:34
	Abhishek Agrawal: 2013-06-07 07:34:53 why i am getting RTE while i am getting right output ID:-9435275 --(ans)--> You can't use square root on bignums : your answer will be a float and you loose 99.9% of precision. Your method is only valid for very small cases. For this problem you have to find a way that don't use bignum. Last edit: 2013-06-07 08:44:33
	Ouditchya Sinha: 2013-06-06 12:22:23 @Franky, I can't seem to optimise my code below 0.24s, any tips? --ans--> SPPC is designed to help you to try some experiments. Good luck. There's too MATEX. RE: Thank you, I'll try to solve them. :) Last edit: 2013-06-06 20:44:42
	Shashi Kant Prasad: 2013-05-11 16:46:59 Is it correct: n=... m=... a= ... c = ... --ans--> No other test case are provided. Last edit: 2013-05-11 18:29:09
	Shashi Kant Prasad: 2013-05-11 15:42:54 Hi Francky, getting WA. Plz, tell me where my soln is failing. My last submission: 9242428 --ans--> Your code is OK for small n, but fails for high ones. Good luck. >> Thanks for response. I corrected some mistakes but still no success. I think, my last submission(id: 9243366) is perfect. --ans--> It is not perfect, and it will be AC when you'll see the green light... ;-) Good luck. >>AC after fixing some Arithmetic errors. @Francky: Thanks, nice problem. Are there medium & hard versions of this problem? >>Michael Kharitonov did extraordinary in this problem, as usual. --ans--> If you want harder than this one, then : DELTACAT and DELTACA2 are made for you. But warning : those are my hardest problems... Last edit: 2013-05-12 15:30:21

Submit solution!

Added by:	Francky
Date:	2013-04-30
Time limit:	1.110s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own problem