## 106 - Fermat vs. Pythagoras

Moderator: Board moderators

New poster
Posts: 3
Joined: Sun Aug 27, 2006 5:40 pm
Location: Dhaka
Contact:
Thanks sohel
I've got AC.

mwiley63
New poster
Posts: 2
Joined: Mon Jan 28, 2008 9:21 pm

I figured out the x y and z values on my own using number theory, just like it is described at the start of the thread, however I had a very tough time making out the bounds for s and r.

Could someone please explain how the bounds were found for s and r to be 1 <= s <= min(sqrt(n-r*r), r-1) and 1 <= r <= sqrt(n)??

I do not understand how this was deduced. For r = sqrt(n) maximum bound, wouldn't r = n/2 be a possible maximum bound for r if you use 1 <= 2rs <= n?

I am unsure and feel uneasy since I do not understand how these bounds were found. I did use these bounds in my program and got a AC, but a cheap one since I didn't come up with them Edit:

I guess I understand how the bound r <= sqrt(n) and s <= sqrt(n-r*r) if you use the r and s forumla for z (since you know that z will be bigger then both x and y). However, I am stumped on where the r-1 comes from in the upper bound on s. (min(sqrt(n-r*r), r-1)).

shantanu18
New poster
Posts: 22
Joined: Tue Jul 20, 2010 9:55 pm

### Re: 106 Fermat Vs Pythagoras 0.1sec!!

I used to generate all primitive PYTHAGOAN triples using Euclidian formula

But All pair of m and n (see this link) does not generate all triples. So i am having problem to generate the second output of this problem. According to Euclidian formula we can get rest of the triples from this equation

a = k * (m^2-n^2) , b = k* (2mn), c = k*(m^2+n^2)

But when i tried to run this K loop (2 to n/c) it takes so much time. Any idea for second output !!!

Code: Select all

``````
#include <cstdio>
#include <iostream>
#include <set>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
#define MAX 1000001
#define int64 long long
using namespace std;
struct node{
int x;
int y;
};
node DP[MAX];
int64 gcd(int64 a,int64 b)
{
if(a==0) return b;
else return gcd(b%a,a);
}
node getValue(int n)
{
if(DP[n].x!=-1) return DP[n];
int cnt,sq;
set <int64> ss;
cnt=0;
int64 a,b,c;
sq=sqrt(n);
for(int64 i=1;i<=sq;i++) //generating all pair of m and n but they do not generate all triples
{
for(int64 j=i+1;(j*j+i*i)<=n;j++)
{
a=j*j - i*i;
b=2*i*j;
c=j*j + i*i;

if(((i%2==0 && j%2!=0)|| (i%2!=0 && j%2==0)) && gcd(i,j)==1){
cnt++;
//cout<<i<<" + "<<j<<"---> "<<a<<" "<<b<<" "<<c<<endl;
}
ss.insert(a);
ss.insert(b);
ss.insert(c);
//cout<<i<<" + "<<j<<"---> "<<a<<" "<<b<<" "<<c<<endl;
}
}

DP[n].x=cnt;
DP[n].y=n-ss.size();
return DP[n];
}
int main()
{
//freopen("106.in","r",stdin);
int n;
memset(DP,-1,sizeof(DP));
while(scanf("%d",&n)==1)
{
node tmp = getValue(n);
printf("%d %d\n",tmp.x,tmp.y);
}
return 0;
}

``````
Please help MartinMSPedersen
New poster
Posts: 1
Joined: Fri Aug 28, 2015 9:56 pm

### Re: 106 - Fermat vs. Pythagoras

Hi,

I quickly made an solution in Java to Problem 106.
On my old computer the program takes 0.3 seconds compute the output for 1000 lines of input.
However when I submit my code it gets "Time Limit exceed".
Very very strange.

Regards
Martin