Read the problem description carefully. The first integer for each output line is the number of relatively prime triples. For example, 3,4,5 are relatively prime or coprime, but 6,8,10 are not. And did you double count the triples? You can also take a look at this website: http://rlevlsi.mit.edu/people/gjcoram/triples.html It has a list of relatively prime triples, where the first number in each triple is < 400. Hope this helps.cthompson wrote:I am working on problem 106, the program seems to work correctly, except my output is different to the sample output.
input:
10
25
100
my output:
1 4
4 9
36 27
sample output:
1 4
4 9
16 27
I tailored the program to print out all the hits to see why I counted 36 and the sample counted only 16. After looking through all of them, I could see no valid reason, does anyone have any insight?
106  Fermat vs. Pythagoras
Moderator: Board moderators
Re: 106  Wrong Examples?

 New poster
 Posts: 28
 Joined: Mon Nov 04, 2002 8:03 pm
 Location: South Korea, Seoul
 Contact:
Please Help me.. Problem 106
I know,
x = r^2  s^2
y = 2 * r * s
z = r^2 + s^2
x^2 = (r^2  s^2)^2 = r^4  2*r^2*s^2 + s^4
y^2 = (2 * r * s)^2 = 4*r^2*s^2
x^2 + y^2 = r^4 + 2*r^2*s^2 + s^4 = (r^2+s^2)^2 = z^2
and i think r, s range is ,
3 <= x < y < z <= n
or
3 <= y < x < z <= n
3 <= r^2  s^2 , 2 * r * s < r^2+s^2 <= n
so,
range of r is 1<= r < sqrt(n)
range of s is
under = max (r^2  3, 0);
upper = min (n/(2*r), r1);
and gcd code is
this code gives correct ouputs in case n<=100 but, n is over then 1000 gives incorrect outputs. maybe incorrect outputs between 100, 1000 ..
please give me outputs in case n>= 500 or 1000 ..
ps. the outputs of this code
x = r^2  s^2
y = 2 * r * s
z = r^2 + s^2
x^2 = (r^2  s^2)^2 = r^4  2*r^2*s^2 + s^4
y^2 = (2 * r * s)^2 = 4*r^2*s^2
x^2 + y^2 = r^4 + 2*r^2*s^2 + s^4 = (r^2+s^2)^2 = z^2
and i think r, s range is ,
3 <= x < y < z <= n
or
3 <= y < x < z <= n
3 <= r^2  s^2 , 2 * r * s < r^2+s^2 <= n
so,
range of r is 1<= r < sqrt(n)
range of s is
under = max (r^2  3, 0);
upper = min (n/(2*r), r1);
Code: Select all
limitR = (int)sqrt(n);
for (r = limitR ; r>=1 ; r )
{
under = max (r^2  3, 0);
upper = min (n/(2*r), r1);
for ( s = under ; s <= upper; s++)
{
x = r*r  s*s ;
y = 2*r*s;
z = r*r + s*s ;
if ( x*x+y*y == z*z && x>0 && y>0 && z>0 && z<=n )
{
if ( ( !check[x1]  !check[y1]  !check[z1] ) && ( gcd(x,y)  gcd(y,z)  gcd(x,z)) )
{
for (k=1 ; k*z <=n ; k++)
{
check[ x*k  1 ] = 1 ;
check[ y*k  1 ] = 1 ;
check[ z*k  1 ] = 1 ;
}
count ++;
}
}
}
}
Code: Select all
int gcd( int x, int y )
{
if ( x > y ) swap(x,y);
while ( x > 0 )
{
y %= x;
swap(x,y);
}
return ( y == 1 ) ;
}
this code gives correct ouputs in case n<=100 but, n is over then 1000 gives incorrect outputs. maybe incorrect outputs between 100, 1000 ..
please give me outputs in case n>= 500 or 1000 ..
ps. the outputs of this code
 1
0 1
10
1 4
100
16 27
1000
156 207
10000
1526 1765
100000
14912 16627
1000000
146039 160508
500
79 110
600
93 131
700
110 147
800
126 166
900
138 183

 New poster
 Posts: 2
 Joined: Thu Jun 10, 2004 6:02 pm
 Contact:
Is there any idea to save time of running problem 106?
My source code has just been accepted, but it took at least 6.3s for running. What I did was:
firstly, I created array to save all relative prime triples ( the number of triples is less than 200000 )
secondly, I read the required number and checked on the array that how many triples which satified the fact that its components are less than or equal the required number.
thirdly, I generated all numbers which can be in any triple which its components are less than or equal required number and I counted which is not used.
That's what I had done. Anybody has some idea to improve?
Thanks a lot.
firstly, I created array to save all relative prime triples ( the number of triples is less than 200000 )
secondly, I read the required number and checked on the array that how many triples which satified the fact that its components are less than or equal the required number.
thirdly, I generated all numbers which can be in any triple which its components are less than or equal required number and I counted which is not used.
That's what I had done. Anybody has some idea to improve?
Thanks a lot.
Nothing to Lose
Re: Problem Fermat vs. Pythagoras(106)  the second number
How do you find all triples?
If you can find all triples include not relatively primes(e.g 6,8,10),
(the second number)=N(the number of all triples)
i hope there are some useful for you...
my English is not well...
If you can find all triples include not relatively primes(e.g 6,8,10),
(the second number)=N(the number of all triples)
i hope there are some useful for you...
my English is not well...
Chocobo, your method is ok, but I think there is another way.
Use an array to mark out numbers used in all triples in the given range, maintaining the count of numbers that are not marked as in a triple. The final count you obtain is the second number.
Using C++ or Java, use a bool(C++) or boolean array. In C, a simple int array is sufficient.
Use an array to mark out numbers used in all triples in the given range, maintaining the count of numbers that are not marked as in a triple. The final count you obtain is the second number.
Using C++ or Java, use a bool(C++) or boolean array. In C, a simple int array is sufficient.
Chocobo said:
The number of all triples with x<y<z and x^2 + y^2 = z^2 is
1 (the only one is 3,4,5). Your method would say then that there are
N  1 = 5  1 = 4 numbers not appearing in triples when the correct
answer is 2.
It's not even safe to say Nnum_triples*3 since some numbers might appear in more than one triple.
This is not true. Let's take a really easy example, N=5.(the second number)=N(the number of all triples)
The number of all triples with x<y<z and x^2 + y^2 = z^2 is
1 (the only one is 3,4,5). Your method would say then that there are
N  1 = 5  1 = 4 numbers not appearing in triples when the correct
answer is 2.
It's not even safe to say Nnum_triples*3 since some numbers might appear in more than one triple.
Ryan Pai wrote:
[Edit] Woops, I see now..all noncoprime triples are scalar multiples of coprime ones. Cool. [/Edit]
Doesn't this only prove that the method generates all relatively prime triples? How do you deal with counting the number of numbers <=N that don't appear in any triple at all? (even the ones that aren't relatively prime).Ok, so why does this generate all triples?
Well, lets assume that x,y,z is a triple which is relatively prime, so not both of x,y can be even...
[Edit] Woops, I see now..all noncoprime triples are scalar multiples of coprime ones. Cool. [/Edit]
this therem does not generate ALL the triples, it generates ALL the relativy prime triples and SOME triples that are not relativy prime.
so you shoud generate all other not relativy prime triples from relativy prime for calculating the number of numbers that are not in any triple.
if you program good the two while cycles it will work. I still don't know why my program is slow, this therem is very "fast", but the program run 8 sec.
good luck
so you shoud generate all other not relativy prime triples from relativy prime for calculating the number of numbers that are not in any triple.
if you program good the two while cycles it will work. I still don't know why my program is slow, this therem is very "fast", but the program run 8 sec.
good luck

 New poster
 Posts: 6
 Joined: Fri Aug 15, 2003 9:12 am

 New poster
 Posts: 6
 Joined: Fri Aug 15, 2003 9:12 am
Help Pleeease... . WA 106  Fermat vs. Pythagoras
Hello guys ... my code for this program solves it correctly.. including the 1000000 but the online judge is insisting on giving me a wrong answer... I guess there is something wrong with how to end the program.. like the eof thingy.. so can anybody check it for me.. show me the way to do it please...
[cpp]
#include <iostream>
#include <cmath>
using namespace std;
bool check(long, long, long);
inline long minim(long a, long b) {
return a<b?a:b;
}
inline bool gcd( long x, long y )
{
long temp;
if ( x > y ) temp = x, x = y, y = temp;
while ( x > 0 )
{
y %= x;
temp = x;
x = y;
y = temp;
}
return ( y == 1 ) ;
}
void main() {
long a, b, x, y, z;
long N, i, limit, under;
long count_triple, count;
while (!cin.eof()) {
cin >> N;
if (N<1) break;
bool *triples = new bool[N];
count_triple = 0;
count = 0;
limit = (long)sqrt(N);
for (a = limit; a > 1; a) {
under = minim((long)sqrt(N(a*a)),a1);
for (b = under; b >= 1; b) {
x = a*a  b*b;
y = 2*a*b;
z = a*a + b*b;
if(check(x,y,z)) count_triple++;
for (i = 1; i*z <= N; i++) {
triples[x*i1] = false;
triples[y*i1] = false;
triples[z*i1] = false;
}
}
}
for (a = 0; a <N; a++) {
if (triples[a]) count++;
}
cout << count_triple << " " << count << endl;
delete [] triples;
}
}
bool check(long x, long y, long z) {
if (gcd(x,y)  gcd(x,z)  gcd(y,z))
return true;
return false;
}
[/cpp]
[cpp]
#include <iostream>
#include <cmath>
using namespace std;
bool check(long, long, long);
inline long minim(long a, long b) {
return a<b?a:b;
}
inline bool gcd( long x, long y )
{
long temp;
if ( x > y ) temp = x, x = y, y = temp;
while ( x > 0 )
{
y %= x;
temp = x;
x = y;
y = temp;
}
return ( y == 1 ) ;
}
void main() {
long a, b, x, y, z;
long N, i, limit, under;
long count_triple, count;
while (!cin.eof()) {
cin >> N;
if (N<1) break;
bool *triples = new bool[N];
count_triple = 0;
count = 0;
limit = (long)sqrt(N);
for (a = limit; a > 1; a) {
under = minim((long)sqrt(N(a*a)),a1);
for (b = under; b >= 1; b) {
x = a*a  b*b;
y = 2*a*b;
z = a*a + b*b;
if(check(x,y,z)) count_triple++;
for (i = 1; i*z <= N; i++) {
triples[x*i1] = false;
triples[y*i1] = false;
triples[z*i1] = false;
}
}
}
for (a = 0; a <N; a++) {
if (triples[a]) count++;
}
cout << count_triple << " " << count << endl;
delete [] triples;
}
}
bool check(long x, long y, long z) {
if (gcd(x,y)  gcd(x,z)  gcd(y,z))
return true;
return false;
}
[/cpp]
Your code doesn't even succeed on the sample input.
input:
your output:
correct output:
For starters you process the last input twice since you check cin.eof() before your cin >> N; statement.
Try changing it to:
I'm not even going to look at the rest of your code, but obviously something is wrong there too.
Good luck
input:
Code: Select all
10
25
100
Code: Select all
1 0
4 1
16 0
16 0
Code: Select all
1 4
4 9
16 27
Try changing it to:
Code: Select all
//while (!cin.eof()) {
//cin >> N;
while (cin >> N) {
Good luck
test data
Some sample data from an ACC program.
INPUT
OUTPUT
I hope it will be useful for someone.
INPUT
Code: Select all
1
2
3
4
5
6
7
8
9
10
11
12
15
20
22
50
55
80
100
500
600
700
800
900
1000
10000
100000
1000000
OUTPUT
Code: Select all
0 1
0 2
0 2
0 2
1 2
1 3
1 4
1 5
1 6
1 4
1 5
1 6
2 5
3 7
3 9
7 15
8 14
12 22
16 27
80 107
95 127
112 142
128 162
140 180
158 205
1593 1669
15919 14844
159139 133926
I hope it will be useful for someone.

 New poster
 Posts: 4
 Joined: Tue Jul 19, 2005 6:32 pm
test data output
Hi Sedefcho,
I do not understand the output of the acc program above. Please help me to understand it!
For an input
the output is
My problem concerns the second number of the output. We know that pythagorian triples 3,4,5 and 6,8,10 exist. The second value of the output is the number of values p, 1 <= p <= N, that are not part of any such triple. So for N = 2..5 an output of two is correct if we consider the first triple 3,4,5. But what about N=6? Why is the output 3, since 6 is part of the next triple? The same for N=7.
Alright, on the other hand one might interpret the second value as the number of values p, 1 <= p <= N, that are not part of any triple x,y,z that can be constructed of values <=N. In that case the output for N=6,7 seems reasonable, but the values for N = 2..5 are not clear to me.
I appreciate any help,
Thanks!
I do not understand the output of the acc program above. Please help me to understand it!
For an input
Code: Select all
1
2
3
4
5
6
7
Code: Select all
0 1
0 2
0 2
0 2
1 2
1 3
1 4
Alright, on the other hand one might interpret the second value as the number of values p, 1 <= p <= N, that are not part of any triple x,y,z that can be constructed of values <=N. In that case the output for N=6,7 seems reasonable, but the values for N = 2..5 are not clear to me.
I appreciate any help,
Thanks!