CHNGFUNC - Editorial

PROBLEM LINK

Practice
Contest

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.

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

alt text

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 :slight_smile: ) -

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 . :slight_smile:

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 :slight_smile: .

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 :slight_smile:

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