Posted:

**Mon Dec 03, 2007 8:08 pm**Thanks sohel

I've got AC.

I've got AC.

The UVa Online Judge board

https://uva.onlinejudge.org/board/

Page **10** of **10**

Posted: **Mon Dec 03, 2007 8:08 pm**

Thanks sohel

I've got AC.

I've got AC.

Posted: **Mon Jan 28, 2008 9:34 pm**

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

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

Posted: **Sat Jun 18, 2011 11:33 pm**

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 !!!

Please help

[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;
}
```

Posted: **Fri Aug 28, 2015 10:04 pm**

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

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