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.
) -