@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-
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() {
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 - CodeChef: Practical coding for everyone
If you like my solution , feel free to give a thumbs up, I need some Karmas .
@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 
.
It can also be done by precomputing all perfect squares and then doing upper bound for each element .
Here is link to the solution : CodeChef: Practical coding for everyone
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
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);
}
}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
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
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
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) CodeChef: Practical coding for everyone
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 : CodeChef: Practical coding for everyone
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)