You are not logged in. Please login at to post your questions!


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

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


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

asked 10 Jul '17, 21:11

prateekg603's gravatar image

accept rate: 0%

edited 24 Jul '17, 00:33

admin's gravatar image

0★admin ♦♦

123next »

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


answered 24 Jul '17, 00:39

phben's gravatar image

accept rate: 9%

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

(24 Jul '17, 15:48) dpraveen ♦♦4★

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

(24 Jul '17, 16:00) vijju123 ♦5★

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 -

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


answered 24 Jul '17, 15:08

rohan_bose95's gravatar image

accept rate: 8%

can you tell me the complexity of your solution?

(27 Jul '17, 21:02) akki284★

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;
    printf("%d\n", ans);
    return 0;

answered 24 Jul '17, 00:32

sun_d's gravatar image

accept rate: 13%

@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


answered 24 Jul '17, 00:41

vijju123's gravatar image

5★vijju123 ♦
accept rate: 19%

edited 24 Jul '17, 00:52

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


answered 24 Jul '17, 00:48

dishant_18's gravatar image

accept rate: 11%

edited 24 Jul '17, 00:49

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.


answered 24 Jul '17, 12:15

swap_49's gravatar image

accept rate: 0%

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


answered 24 Jul '17, 17:27

rohan_bose95's gravatar image

accept rate: 8%

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


answered 25 Jul '17, 11:34

sidd845's gravatar image

accept rate: 0%

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?


answered 24 Jul '17, 11:21

shubamg's gravatar image

accept rate: 0%

edited 24 Jul '17, 11:22


(25 Jul '17, 20:20) phben6★

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;

answered 24 Jul '17, 13:20

chan55555's gravatar image

accept rate: 6%

edited 24 Jul '17, 16:27

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

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

(24 Jul '17, 16:24) vijju123 ♦5★

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

(24 Jul '17, 16:24) chan555553★

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

(24 Jul '17, 17:02) chan555553★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 10 Jul '17, 21:11

question was seen: 2,198 times

last updated: 31 Mar, 16:51