I was solving this question Pythagorean Theorem II
and saw some optimized solution based on this relation seems
Saw some solved optimized codes using this relations seems gcd(a,b,c)=1
int n,m=0;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;(i*i+j*j<=n&&i>j);j++)
{
if((i-j)%2==1)
if(gcd(i,j)==1)
m+=n/(i*i+j*j);
}
}
cout<<m;
I know a,b,c are relatively prime but is it enough to know that ?
Can somebody tell me proof of this approach ?
https://en.wikipedia.org/wiki/Pythagorean_triple
I think the code you posted uses the fact that if a^2+b^2 = c^2, then k*a^2 + k*b^2 = k*c^2 for every positive integer k, so you only need to check the triples that have a gcd of 1 and count every multiple of those numbers until they become greater than n (which can be done in O(1) by dividing n by the biggest number).
thanks bro