CHNGFUNC - Editorial






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




Math, Number Theory


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


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


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

     for i = 1 to B
         j = i
         while j <= B
            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.

         for i = 1 to sqrt(B)
             j = i
             while j <= B
                 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]* and y/divisor[y]* 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]* 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


Author’s solution can be found here.
Tester’s solution can be found here.


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 {
        if(!flag) break;

", ans);
return 0;


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


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

Image of derivation-

alt text


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


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.


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() {
    long long a,b,i,ans=0;
        ans+=(long long)sqrt(((double)b/(i*i))+1)-1;

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 -

If you like my solution , feel free to give a thumbs up, I need some Karmas . :slight_smile:


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


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

Here is link to the solution :


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:


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)

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


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

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)
			float p = (m+n)/2f;
			float x = (m-n)/2f;
			if(((p - (int)p) == 0) && ((n - (int)n) == 0) &&
                                      (x >=1) && (x <= a)){
	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);
			if(j/i != i && j/i > Math.sqrt(b))
	return divisors;
public static void main(String[] args) {
	Scanner scan = new Scanner(;
	int a = scan.nextInt();
	int b = scan.nextInt();
	int count=countSquares(a,b);		


i submitted my solution during contest, it throws TLE at that time.
But when i copy pasted my code(exactly same) in practice section it gave me AC.can anyone explain why this happened?


i submitted my solution during contest, it throws TLE at that time.
But when i copy pasted my code(exactly same) in practice section it gave me AC.can anyone explain why this happened?


My solution is a bit different.At first, I pre-computed all squares of numbers up to 10000002.Then for each square number let say x less than A*A,I searched how many square numbers are there in the region x+B.Here is my solution text


In #Author’s solution why do we check for (k_plus_x + k_minus_x)%2==0 && (k_plus_x - k_minus_x)%2==0???


CHNGFUNC In #Author’s solution why do we check for (k_plus_x + k_minus_x)%2==0 && (k_plus_x - k_minus_x)%2==0 ???


i think this one is easy and simple to understand my solution which i tried after contest Time complexity: O(A)