×

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

20421223
accept rate: 0%

19.8k350498541

 7 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 6★phben 149●3 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) 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)
 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 - https://www.codechef.com/viewsolution/14658471 If you like my solution , feel free to give a thumbs up, I need some Karmas . :) answered 24 Jul '17, 15:08 602●1●5 accept rate: 8% can you tell me the complexity of your solution? (27 Jul '17, 21:02) akki284★
 2 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 #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; }  answered 24 Jul '17, 00:32 2★sun_d 127●5 accept rate: 13%
 2 @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- answered 24 Jul '17, 00:41 15.5k●1●20●66 accept rate: 18%
 1 When you notice you got WA just because of int instead of long long ;_; answered 24 Jul '17, 00:48 614●1●9 accept rate: 12%
 1 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 1★swap_49 11●1 accept rate: 0%
 1 @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 602●1●5 accept rate: 8%
 1 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 3★sidd845 25●4 accept rate: 0%
 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 5★shubamg 1●1 accept rate: 0% $\sum_{i=1}^{n}\frac{1}{i}=O(log(n))$ (25 Jul '17, 20:20) phben6★
 0 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 #include #include #include #include #include #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<=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) Anyone, please help!! I couldn't find what's wrong with my solution. (24 Jul '17, 16:24) @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)
 0 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 answered 24 Jul '17, 23:43 164●9 accept rate: 4%
 0 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 answered 25 Jul '17, 13:24 3●2 accept rate: 0%
 0 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> divisors = precomputeDivisors(b); int count = 0; for(int y = 1; y <= b; y++){ List 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> precomputeDivisors(int b){ Map> divisors = new HashMap<>(b+1); for(int i = 1; i*i <= b; i++ ){ for(int j = i; j <= b; j+=i){ List 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); } } ` answered 25 Jul '17, 20:02 1 accept rate: 0%
 0 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? https://www.codechef.com/viewsolution/14675999 https://www.codechef.com/viewsolution/14656596 answered 26 Jul '17, 22:32 11●1 accept rate: 0%
 0 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? https://www.codechef.com/viewsolution/14675999 https://www.codechef.com/viewsolution/14656596 answered 26 Jul '17, 22:32 11●1 accept rate: 0%
 0 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 link.link text answered 27 Jul '17, 21:44 4★shadow10 11●2 accept rate: 0%
 0 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?????? answered 29 Jul '17, 04:14 1●1 accept rate: 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 ??????

This answer is marked "community wiki".

11
accept rate: 0%

 0 i think this one is easy and simple to understand my solution which i tried after contest Time complexity: O(A) https://www.codechef.com/viewsolution/14762782 answered 02 Aug '17, 23:50 1 accept rate: 0%
 0 I used two pointer technique. First I stored all the squares till the maximum possible perfect square one can get in a vector. Then I used the difference of values of two pointer to check the condition |x^2-y^2|<=b. My solution : https://www.codechef.com/viewsolution/17996226 answered 31 Mar '18, 16:50 30●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,852
×1,723
×1,220
×639
×56
×6

question asked: 10 Jul '17, 21:11

question was seen: 2,648 times

last updated: 31 Mar '18, 16:51