PELL2 - Pell (Mid pelling)

no tags 

D is a given positive integer, consider the equation :
X² = D×Y² + 1, with X and Y positive integers.
Find the minimum numbers (X,Y) within all solutions.
Sometimes it's possible, sometimes not!

Examples :
If D=2, 3² = 2×2² + 1, so X=3 and Y=2.
If D=3, 2² = 3×1² + 1, so X=2 and Y=1.
If D=4, it's impossible!


The input begins with the number T of test cases in a single line.
In each of the next T lines there is one integer D.


For each test case, if possible print X and Y the answer of the problem for D, else "-1".



3 2
2 1


T <= 1000
1 < D <= 10^7, the numbers D were randomly chosen. (but XerK modified one of them!)
190 bytes of sub-optimal python code can get AC in less than 2.5 seconds, there's many rooms to make faster code.
If you have TLE, you should first consider EQU2 first.

Edit(2017-02-11, after compiler updates) : New TL at 1.5s. The Python awaited solution ends under 0.8s, pike or java around 1.4s. Some old AC might not keep their AC : here it's mid-pelling. The 'mid' is to be kept in consideration.

hide comments
Prime: 2015-12-15 05:02:37

Does the answer exceed 10^1000?
=(Francky)=> Sometimes, yes.

Last edit: 2015-12-15 09:50:48
Francky: 2014-12-22 00:29:16

Edit : I didn't merge no more the rank list. All comments set at this time, after this change.

(Tjandra Satria Gunawan)(曾毅昆): 2014-12-22 00:27:58

@Francky: I wonder why you don't solve any problem for more than last 2.5 months?
--ans--> I'm working hard for an exam I've missed by a little point, I'll have another chance next year, and I want to be in the top. I keep an eye on your exploits and I hope I'll can finish my new hardest project, frozen in the middle by my fail at THE exam. It will be a giant problem, you can be sure.

Last edit: 2013-07-29 15:33:40
[Lakshman]: 2014-12-22 00:27:58

@Francky can you please suggest me if I am doing some thing wrong. Getting TLE, I tried the same code for EQU2 and got AC in just .04 seconds, Or my algorithm is slow?
--ans--> "while something not in otherthing:" is very slow, you should avoid that. Good luck.

Last edit: 2013-07-28 16:22:47
Aditya Pande: 2014-12-22 00:27:58

--ans--> Didn't you said that Ruby was faster than Python ? So your algo should be improved. Hint : the title is mid-pelling, and there's many rooms for optimization ...

edit: ya my algo should be faster for this but this is the best i could have come up with. Thank u

Last edit: 2012-12-19 13:47:01
Ehor Nechiporenko: 2014-12-22 00:27:58

Really nice math problem

(Tjandra Satria Gunawan)(曾毅昆): 2014-12-22 00:27:58

I need fast I/O to solve this, wait until I master dynamic bignum in C ;-)
--ans--> No you don't need, I don't like force people with fast IO. this problem can be solved under 2.5s with ultra basic python code (less than 200bytes), and under 1s with some tricks. Quite the same with a C-like language. Have fun.

Last edit: 2012-11-15 19:55:02

Added by:Francky
Time limit:1.75s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Old problem