106 - Fermat vs. Pythagoras

[riyad_csedu]

Thanks sohel
I've got AC.

[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

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]

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;
	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]

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