PROBLEM LINKCONTEST PANELAuthor: Prateek Gupta DIFFICULTYEasyMedium PREREQUISITESMath, Number Theory PROBLEMFind the number of integral pairs $(x,\ y)$ such that ($x^{2}\ +\ y$) is a perfect square where $x$ varies from $[1,\ A]$ and $y$ varies from $[1,\ B]$. EXPLANATIONLet us iterate over both the approaches for smaller and bigger constraints. Approach for A, B $≤$ 10^3Here, we can easily do a brute force to check for each pair $(x, y)$ such that $x\ ≤\ A$ and $y\ ≤\ B$ and see if that pair fits into the equation. Let us see the pseudo code for this brute approach.
Overall complexity for this solution will be O(A*B) which is atmost $10^{6}$ operations in worst case scenario. But, this solution is too slow for the bigger constraints where we will need to think little differently. Approach for A, B $≤$ 10^6Let $F(x, y) = k$ where $k$ is any integer. $$\implies x^{2} + y = k$$ Now, according to the question, $k$ should be a perfect square. $$\implies k = p^{2}$$ $$\implies x^{2} + y = p^{2}$$ Converting the above equation into more simpler form, it can be rewritten as
$$y = p^{2}  x^{2}$$
$$OR$$
$$y = (p + x)(p  x)$$
Since, $y$ $\in$ $[1, B]$, for each such y, we can find it's divisors {$m_{i}, y/m_{i}$} and try to match it with $(p + x)$ and $(p  x)$. More formally, $$p + x = m_{i}$$ $$p  x = y/m_{i}$$ The above two equations can be solved to get the value of $p$ and $x$. Both $p$ and $x$ obtained should be integral values and $x$ should $\in$ range $[1, A]$. Since, you will need to iterate over all divisors of each $y$ from $1$ to $B$, $O(B*sqrt(B))$ will turn out to be a little slow in the given time limit. The best way out here is to precompute the divisors using Sieve of Eratosthenes. Let us now have a look at the pseudo code.
However, this is still a little slow to get fit within the time limit. The above algorithm takes $O(B*log(logB))$ time for precomputation.The sieve implementation to store the divisors for each number can be optimized further to achieve best possible results. We do not really need to iterate uptill $B$ to precompute the divisors upto $B$. Infact, iterating till $sqrt(B)$ is sufficient. Why? You might think that we can miss divisors $>$ $sqrt(B)$ for some numbers. But, you will never miss those since you will always have a divisor $≤$ $sqrt(B)$ from which you can always find it's counterpart by dividing the divisor from the number itself. Now, let us have a look at the pseudo code to make things clear.
This allows us to achieve the complexity of $O(sqrtB*log(logB))$. Now, you can put the value of $m_{i}$, once as $divisor[y][i]$ and $y/divisor[y][i]$ next, in the above equation to find if there exist possible valid values of $p$ and $x$. You go on doing this for each $divisor[y][i]$ and for each $y$ from $1$ to $B$. For more and precise details on the implementation, please refer to the setter's or tester's solution SOLUTIONSAuthor's solution can be found here. asked 10 Jul '17, 21:11

Here is my solution (and its quite simple to understand :) )  As x^2 + y = p^ 2 thus y = p^2  x^2 ,for x to be in [1,A] and y in [1,B]. (where p^2 is a perfect square) As y can't be zero or negative then, p should be greater than x+1. Thus p can take up any integer from x+1 to infinity such that p^2  x^2 <= B. Thus we need to find for each x in [1,A] the number of integral points of p which are greater than or equal to x+1 and satisfies the equation p^2  x^2 <= B. Here is my code  https://www.codechef.com/viewsolution/14658471 If you like my solution , feel free to give a thumbs up, I need some Karmas . :) answered 24 Jul '17, 15:08

Nice question. Took a while to figure it out. But then it became one of the best submissions. I did it as follows with much less code but very efficient.
answered 24 Jul '17, 00:32

@phben exactly!! The editorial's solution seems a bit complicated. There is a beautiful O(A) solution possible if we use concepts of A.P. and quadritic equation!! My code for reference https://www.codechef.com/viewsolution/14650629 Image of derivation answered 24 Jul '17, 00:41

When you notice you got WA just because of int instead of long long ;_; answered 24 Jul '17, 00:48

Many of the solutions whose time complexity is O(a*b) have been accepted.They have been given partial points. All the solutions to this questions should be rejudged. answered 24 Jul '17, 12:15

@chan55555 Here is how i would like to explain the bug in your solution. As you have assumed y=(n^2  1)x^2 .. this implies y = (n * x)^2  (x)^2 i.e x^2 + y = (n * x)^2 Thus according to you the perfect squares can be only those squares whose square roots are multiples of x while there was no such restriction in the problem statement itself. This assumption will leave a lot possible perfect squares whose square roots are not multiples of x. An example would explain this more clearly . if A=4 and B=6 then there would be a case of (x,y) as (2,5) i.e 2^2 + 5 = 9 ., as you can see that the 9 isn't a multiple of 2 , thus your program wont take 9 into consideration and hence would leave out a possible (x,y) pair , thus the ans produced by your code will be less than (or in some special cases equal to ) the correct answer . The correct answer for A=10000 B=100000 is 291528 but ur code produces 1591 .. thus leaving out a lot of possible cases. I Hope this makes it clear . You can refer to my solution in the comments above. If you like my comment , feel free to give a thumbs up , I need some Karmas :) . answered 24 Jul '17, 17:27

i used binary search for this! now , i used binary search to find the upper bound of a (satisfying the constraint on y) and do the same for all x . my solution got accepted but if anyone thinks any bug in approach then please let me know :) answered 25 Jul '17, 11:34

Can anybody please explain that how the time complexity of last algorithm given in the editorial is $\sqrt{B}$lg(lg(B))? I came up with the following analysis for time complexity: $\sum_{i=1}^{\sqrt{B}}\frac{B}{i} = B$log($\sqrt{B}$) Can somebody please explain? answered 24 Jul '17, 11:21

Can anybody point out what is wrong with my approach?? Since we have to make $x^2+y$ as a perfect square, so, we can write $y=(n^21)x^2$ where $n>=2$. We try to find out that for a particular value of $x^2$, how many $n^21$ terms are possible or can say how many $n$ are possible. Since maximum value of $y$ is $B$, so, $n=\sqrt{B/{x^2}+1}1$. ($B/x^2$ is real number division not integer division) Here $n$ has $1$ term because $n$ starts from $2$ not from $1$.So, for each value of $x^2$ we try to find no. of values of $y$.
answered 24 Jul '17, 13:20
Does this not imply that y HAS to be a integral multiple of x? And its not the case, say for x=2 and y=5. y cannot be expressed as y= (nn1)x [where n is integer] but it forms a square. It looks like your approach misses out some cases. What do you think?
(24 Jul '17, 16:24)
Anyone, please help!! I couldn't find what's wrong with my solution.
(24 Jul '17, 16:24)
@vijju123 Yeah!! I got it. My solution was only considering the integral value of $n$ but the fractional value of $n$ does also contribute to the answer.
(24 Jul '17, 17:02)
