106 - Fermat vs. Pythagoras

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

New poster
Posts: 3
Joined: Sun Aug 27, 2006 5:40 pm
Location: Dhaka

Post by riyad_csedu »

Thanks sohel
I've got AC.

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

Post by mwiley63 »

I have a quick question about this problem.

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 :(


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

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

Re: 106 Fermat Vs Pythagoras 0.1sec!!

Post by shantanu18 »

I used to generate all primitive PYTHAGOAN triples using Euclidian formula
[link] http://en.wikipedia.org/wiki/Pythagorean_triple [/link]

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;
	int64 a,b,c;
	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;
			c=j*j + i*i;
			if(((i%2==0 && j%2!=0)|| (i%2!=0 && j%2==0)) && gcd(i,j)==1){
				//cout<<i<<" + "<<j<<"---> "<<a<<" "<<b<<" "<<c<<endl;
			//cout<<i<<" + "<<j<<"---> "<<a<<" "<<b<<" "<<c<<endl;
	return DP[n];
int main()
	int n;
		node tmp = getValue(n);
		printf("%d %d\n",tmp.x,tmp.y);
	return 0;

Please help :(

New poster
Posts: 1
Joined: Fri Aug 28, 2015 9:56 pm

Re: 106 - Fermat vs. Pythagoras

Post by MartinMSPedersen »


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.


Post Reply

Return to “Volume 1 (100-199)”