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