### PROBLEM LINK

### CONTEST PANEL

**Author**: Prateek Gupta

**Tester**: Praveen Dhinwa

**Editorialist**: Prateek Gupta

### DIFFICULTY

Easy-Medium

### PRE-REQUISITES

Math, Number Theory

### PROBLEM

Find 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].

### EXPLANATION

Let us iterate over both the approaches for smaller and bigger constraints.

### Approach for A, B ≤ 10^3

Here, 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.

```
ans = 0
for x = 1 to A
for y = 1 to B
if ( perfect_square(x*x + y) ) ans = ans + 1
print(ans)
```

Overall complexity for this solution will be O(A*B) which is at-most 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^6

Let F(x, y) = k where k is any integer.

Now, according to the question, k should be a perfect square.

Converting the above equation into more simpler form, it can be re-written as

Hence, y can be written as a product of two integers i.e (p + x) and (p - x). It is now easier to formulate the solution based on this.

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,

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.

```
precompute(B)
{
for i = 1 to B
j = i
while j <= B
divisors[j].push_back(i)
j = j + i
}
```

However, this is still a little slow to get fit within the time limit. The above algorithm takes O(B*log(logB)) time for pre-computation.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.

```
precompute(B)
{
for i = 1 to sqrt(B)
j = i
while j <= B
divisors[j].push_back(i)
if ( j/i != i && j/i > sqrtB ) divisors[j].push_back(j/i)
j = j + i
}
```

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

### SOLUTIONS

Author’s solution can be found here.

Tester’s solution can be found here.