Hi
I am solving a problem that is conceptually simple.
Given an integer x, such that 1 ≤ x ≤ 1017, check if v = 5x2 + 2x + 1 is a perfect square. I have solved this using Big Integers and long doubles in C++ (with a binary search to find the root) and used PyPy to get it accepted in Python but I did not receive satisfaction in solving it this way.
Also, __int128 do not work on SPOJ for some reason :/
I think Big Integer may be an overkill for such a problem and the uncertainty with floating point precision is never re-assuring. Hence, my question is, is there any way to solve this problem without Big Integers or long doubles in C++?
Thanks
So then we iterate over the divisors of 2x, say 2x = d1 × d2 and check if a = d1 and b = d2 gives us a Pythagorean triplet? Won't this take upto 108.5 operations?
What if we have to answer multiple queries, say upto 100000 of them?
As far as I know you can approximate the number of divisors with
for numbers ≤ 1018, so this solution will work if you factorize x + 1 and 2x in 
time.
Thought it doesn't fit your new limit of 105 queries
I think that is just to count the number of divisors and not explicitly factor them...
Why not? Prime factorization will allow you to generate every divisor recursively.
It can be done in
by Pollard's rho algorithm.
Maybe you can try to solve further, (I didn't do that, not sure if it may be finished),
ab = x, a2 - b2 = x + 1 = ab + 1, so we can find function a(b) as solution of quadratic and may be we can do something clever.
UPD: a2 - (x / a)2 = x + 1 is biquadratic but numbers may get big again:(
UPD2: It seems that it's equivalent to find square root you need to find:(
Try this.
Maybe for large numbers there exists a counterexample, and you must use a random prime numbers that's still less than 109.
Isn't this a randomized algorithm? Also, did you generate this sequence of primes similar to how primes are chosen for the Miller Rabin test or was this just trial and error till it worked?
I think so. Because for prime p there are half of residues modulo p is square residues and isPerfectSquare give you false positive error with probability 1 / 2. But may be product of all prime numbers should be greater than v.
FWIW I'd go with long doubles for this — it's not hard to prove that the precision is enough. If we compute "y = sqrt(5*x*x + 2*x + 1)" as a long double, we get a ~57-bit number, and the error should be low (at most a 1-ulp error resulting from the large multiplication, 1 from the addition, and 1 from the sqrt, and addition and sqrt both give additive errors). The mantissa of long doubles is 64 bits, so we'll always be within 2^(57 — 64) * 3 = ~0.02 of the right answer. So if v is a perfect square, "z = (long long)round(y)" will be correct.
Then just check that "z*z == 5*x*x + 2*x + 1" modulo distinct primes with large enough product, per CRT.