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 >

	Mukund Kumar: 2013-05-11 08:03:54 @Author:I am getting segsegv...finding a and c with 22 matrix..What should i do?any suggestion is welcomed.. --ans--> Sorry, but there are several problems in your code, you should try easier problems first. Finally AC ;) Last edit: 2013-05-12 10:17:04*
	Arika Saputro: 2013-05-10 10:36:50 @francky i don't know why giving WA, can you check my code? 9234156 --ans--> I've check your code, and there's a little error in it. You're very near. You should make some test with small n and various moduli... --ans--> phew.. ;-) finally ac.. thanks for this problem francky, super nice problem for me, i learn something new ;-) Last edit: 2013-05-11 03:33:12
	arko: 2013-05-08 19:24:18 still getting a WA converted float to double...can't figure out wat is wrong in my code --ans--> 'doubles' are too floating point numbers, all those containers don't suit for this problem. You need to work with modular arithmetic and only integers. Last edit: 2013-05-10 11:34:19
	Michael Kharitonov: 2013-05-05 13:14:45 Why (0,1,1) is not in S? It must be in S by defenition. --ans--> In France 0 is both positive and negative, so I thought non negative means strictly positive, so 0 is not non negative. If non negative means >=0, I'll edit. edit : I've checked, and in English nonnegative means >=0, and as I want >0, I'll set "positive". Thanks for your catch. Last edit: 2013-05-05 13:28:07
	Ouditchya Sinha: 2013-05-05 07:27:23 Please check my code ( ID : 9205199 ). I'm getting correct answers for given test cases but WA here. What is the output for 1000000000000000000 1000000000? --ans--> You're very near for AC, no other test cases are provided. Good luck. RE: Can you please atleast tell whether it's overflow error or some tricky test case. :) --ans--> I recommend you to make some intensive check with small moduli and small n ; it's not overflow, your code is over-protected on this side. ;-) RE: Finally AC, Thank you for this awesome problem, I learnt a lot from this. Thank you again for the hint. I'm the 9th user to solve this, a lot of optimisations are possible to improve speed. I will definitely try them. :) Last edit: 2013-05-14 15:02:42
	Hasan Jaddouh: 2013-05-03 20:58:46 I can't understand the third testcase, sqrt(118^2 + 119^2) is not an integer. Edit: ok got it 696 mod 289 Last edit: 2013-05-03 21:06:11
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-05-02 18:51:08 I'm not advanced python or pascal user.. but at least I got AC :-) --ans--> I have faster IO in Python, it's true, but my algo is better in this way : per case, if we only count * and % operations, I do : [ (1,1%)/2 + (4,2%) ] * log2(n) + epsilon You do: [ (4,2%)/2 + (4,3%) ] * log2(n) + epsilon This is why I am faster. ;-) Congratulations for your translations, and you are an advanced user in general! Last edit: 2013-05-02 19:26:39
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-05-01 20:17:47 "With wisfaq observation, all my best timings are divided by exactly two!!!" I think I know what it means ;-) --ans--> Exact!!! My new code is quasi the same than yours, congratulations. I'll try it on huge input and give you precise comparison if you want. (edit) With T<10^6 (29MB of input), my best time is 2.416s, yours is 3.160s on my hardware. Now you have THE fast method, you should try a python edition... Congratulations again. You can delete this message if you want ;-) Edit(Tjandra): Thanks for the info, I'll try the python edition and pascal edition tomorrow.. :-D I like this kind of problem, but I still don't have idea to solve DELTACAT.. I know that problem is "generalization" of this problem, I still working with my slow brute-force program to find pattern, but still no luck.. Last edit: 2013-05-01 20:49:57
	arko: 2013-05-01 17:00:45 why wrong answer? its coming right for every test case I tried --ans--> You can't use float to store full precision numbers as your algo requires. Last edit: 2013-05-01 17:46:06
	Arika Saputro: 2013-04-30 16:41:59 why sigsegv? --ans(francky)--> In the constraints, you can see n under 10^18, it's too high for your recursive attempt. Good luck for another approach ;-) --ans(arika)--> it's make me confused, i can find c with 22 matrix, but to find a,there are 2 conditions and i don't know how to calculate it using matrix, i will try other solution, it's nice prob ;D Last edit: 2013-05-09 04:28:19*

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