SPOJ.com - Problem DELTACA2

DELTACA2 - Delta catheti II (Hard)

(3, 4, 5) is a famous Pythagorean triple, it gives a quick answer to the question:
For a given integer d, is there a Pythagorean triple (a, b, c) such that b - a = d?

A solution is (3d, 4d, 5d), and in fact one can easily prove that the set of solutions is infinite, and that there is an obvious total order on those solutions.
Given n, you'll have to find the nth term of the sequence of solutions.

Geometrically, it is the study of right angle triangles for which the difference of the catheti is equal to d.

Input

The first line of input contains an integer T, the number of test cases.

2T lines follow. Each case is on two lines.
The first line of the case contains three integers n, d, m.
The second line contains an integer L and 2L other integers (p, e) ; this gives the prime factorization of d in standard format (d = product p^e).

Output

For each test case, compute the nth term amongst the solutions (a, b, c) for the problem :
a² + b² = c² with b - a = d and 0 < a < b < c .

As the answer could not fit in a 64-bit container, simply output your answer modulo m.

Example

Output:
3 4 5
63 84 105
5 3 1

Explanations

For the first case, the first solution is (3, 4, 5), as 4 - 3 = 1.

For the second case, the first solutions are:
(15, 36, 39), (24, 45, 51), (63, 84, 105), (144, 165, 219), (195, 216, 291), (420, 441, 609), ...
The third one is (63, 84, 105).

For the third case, the first solutions are:
(24, 143, 145), (49, 168, 175), (57, 176, 185), (85, 204, 221), (136, 255, 289), (180, 299, 349), (196, 315, 371), (261, 380, 461), (357, 476, 595), (481, 600, 769), (616, 735, 959), ...
The 9th solution is (357, 476, 595), reduced modulo 11, we get (5, 3, 1).

Constraints

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

d is the product of two integers lower than 10^7.
n, d₁, d₂, m : Uniform randomly chosen in their range.
Those constraints are set to allow C-like users to work only with 64bit containers.

For your information, my 3kB-python3 code get AC in 1.22s. (Edit 2017-02-11, after compiler change)
It should be much faster with a compiled language.
Warning : It's my hardest problem. Have fun ;-)

Submit solution!

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

hide comments



2023-11-17 07:26:05 Oleg nitpick: Seems constraints about d1, d2 and "d is the product of two integers" are outdated. There are cases with more than 2 factors. [Francky]-> "d is the product of two intergers" ; Nobody wrote those two are primes. Constraints are good and designed to help solvers! Last edit: 2023-12-14 19:00:18
2023-05-01 22:40:23 Francky I like when a problem doesn't belong to another one if it's not an obligation. Here I like one can solve it without struggling with optimized factorization, and yes many would be able to do that, but maybe not using Python. The problem is hard enough and interesting without the factorization part. Thanks to BM for the quick answer. As a challenge, anybody can try to solve it with its own factorization method and claim the success ; I will congrats any such solver.
2023-04-13 04:23:46 [Rampage] Blue.Mary The reason why the author gives the factorization of d is just to reduce the complexity of coding (especially in Python). Do not think of all problems only in terms of time complexity, in SPOJ coding complexity is also a significant issue.
2023-04-12 14:57:45 Ishan It's strange that you are giving d as well at its prime factorization. I understand that you may have given the factorization, since you want the time complexity to be lesser than factoring time, my point was the first d was not required, But given the numbers and time limit, now I feel even factoring should be doable within the same time. Isn't it ? Last edit: 2023-04-12 15:11:30
2013-06-11 18:26:12 Francky Congratulations to Robert Gerbicz as the first solver.