# CHNGFUNC - Editorial

### CONTEST PANEL

Author: Prateek Gupta
Tester: Praveen Dhinwa
Editorialist: Prateek Gupta

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.

\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 re-written as

y = p^{2} - x^{2}
OR
y = (p + x)(p - x)

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,

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.

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.

1 Like

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.

#include <stdio.h>
#define gc getchar_unlocked

int rin() { char c = gc(); while(c<'0' || c>'9') c = gc(); int ret = 0; while(c>='0' && c<='9') { ret = 10 * ret + c - 48; c = gc(); } return ret; }
int main() {
int A = rin(), B = rin(),x,y, ans = 0,i, a, flag = 0;

for(a = 1;;a++){
flag = 0;
for(x =1;x<=A;x++){
y = 2*a*x + a*a;
if(y<=B) ans++, flag = 1;
else {
break;
}
}
if(!flag) break;
}
printf("%d\n", ans);

return 0;
}
2 Likes

Actually there is also a O(A) solution: for each a between 1 and A, you find how many integers say c_a between $\sqrt{a^2+1} and \sqrt{a^2+B}. The answer is \sum_{a=1}^{A}c_a$.

7 Likes

@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-

2 Likes

When you notice you got WA just because of int instead of long long ;_;

1 Like

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?

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.

1 Like

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^2-1)x^2 where n>=2. We try to find out that for a particular value of x^2, how many n^2-1 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.
Here is my code.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>

#define pb push_back
using namespace std;

int main() {
ios_base::sync_with_stdio(0);
long long a,b,i,ans=0;
cin>>a>>b;
for(i=1;i<=a;i++)
ans+=(long long)sqrt(((double)b/(i*i))+1)-1;
cout<<ans<<"\n";
return 0;
}

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 .

5 Likes

Really neat solution!! My (tester’s) solution is based on the fact that the bound on answer won’t be large.

Yup, this approach is really neat. I think its like, less than 10 lines of code (ignoring headers and stuff)

write y=(n2−1)x2y=(n2−1)x2 where n>=2n>=2.


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= (n*n-1)*x [where n is integer] but it forms a square.

It looks like your approach misses out some cases. What do you think?

Anyone, please help!! I couldn’t find what’s wrong with my solution.

@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.
for example your case of x=2 and y=5, n=1.5 does also contribute to the answer.
Thank you for the test case!!

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

1 Like

It can also be done by precomputing all perfect squares and then doing upper bound for each element .

Here is link to the solution : https://www.codechef.com/viewsolution/14654083

i used binary search for this!
x^2 + y = a^2
=> y = a^2 - x^2;

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

1 Like

Wait Wait! The approach actually worked? In my case it didn’t seem to do so. (Yes, I use Java)

The optimal solution is O(A * log B)

https://www.codechef.com/viewsolution/14651473

The other O(a*b) feels kinda unfair tho

The editorial solution didnt work fr me… I am gettng TLE…

import java.io.*;
import java.util.*;
class PerfectFunction {
public static int countSquares(int a, int b){
Map<Integer,List<Integer>> divisors = precomputeDivisors(b);
int count = 0;
for(int y = 1; y <= b; y++){
List<Integer> list = divisors.get(y);
for(int i : list){
int m = i;
int n = y/m;
if(m < n)
continue;
float p = (m+n)/2f;
float x = (m-n)/2f;
if(((p - (int)p) == 0) && ((n - (int)n) == 0) &&
(x >=1) && (x <= a)){
count++;
}
}
}
return count;
}
public static Map<Integer,List<Integer>> precomputeDivisors(int b){
Map<Integer,List<Integer>> divisors = new HashMap<>(b+1);
for(int i = 1; i*i <= b; i++ ){
for(int j = i; j <= b; j+=i){
List<Integer> list = divisors.get(j);
if(list == null){
list = new ArrayList<>();
divisors.put(j, list);
}
list.add(i);
if(j/i != i && j/i > Math.sqrt(b))
list.add(j/i);
}
}
return divisors;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int a = scan.nextInt();
int b = scan.nextInt();
int count=countSquares(a,b);
System.out.println(count);
}
}

\sum_{i=1}^{n}\frac{1}{i}=O(log(n))