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

### Re: 106 - Wrong Examples?

Posted: **Wed Apr 28, 2004 4:39 pm**

by **chunyi81**

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?

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://rle-vlsi.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.

### Please Help me.. Problem 106

Posted: **Fri May 21, 2004 7:58 am**

by **Gaolious**

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), r-1);

Code: Select all

```
limitR = (int)sqrt(n);
for (r = limitR ; r>=1 ; r-- )
{
under = max (r^2 - 3, 0);
upper = min (n/(2*r), r-1);
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[x-1] || !check[y-1] || !check[z-1] ) && ( 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 ) ;
}
```

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

- 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

ps. it's same outputs in limitR = sqrt(n)+1, under=1 and upper=r

Posted: **Mon May 24, 2004 6:56 am**

by **pentium8**

I don't know

It's too difficult~

Posted: **Mon May 24, 2004 10:51 am**

by **chunyi81**

Try using unsigned long (this is equivalent to a 64 bit integer).

### Is there any idea to save time of running problem 106?

Posted: **Mon Jul 12, 2004 2:27 pm**

by **NothingElse**

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.

### Re: Problem Fermat vs. Pythagoras(106) - the second number

Posted: **Thu Jul 29, 2004 8:52 am**

by **Chocobo**

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

Posted: **Thu Jul 29, 2004 10:35 am**

by **chunyi81**

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.

Posted: **Mon Aug 02, 2004 2:35 pm**

by **Minilek**

Chocobo said:

(the second number)=N-(the number of all triples)

This is not true. Let's take a really easy example, N=5.

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 N-num_triples*3 since some numbers might appear in more than one triple.

Posted: **Mon Aug 02, 2004 2:48 pm**

by **Minilek**

Ryan Pai wrote:

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

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

[Edit] Woops, I see now..all non-coprime triples are scalar multiples of coprime ones. Cool. [/Edit]

Posted: **Sat Aug 28, 2004 11:19 pm**

by **Sasko**

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

Posted: **Fri Sep 24, 2004 5:39 am**

by **palespower**

I guess. u have a mistake in defining the limits of s....

variable under should be always 1

and variable upper should be min(sqrt(N-r*r), r-1)

Try those modifications .. I hope this helps

### Help Pleeease... . WA 106 -- Fermat vs. Pythagoras

Posted: **Fri Sep 24, 2004 6:01 am**

by **palespower**

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)),a-1);

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*i-1] = false;

triples[y*i-1] = false;

triples[z*i-1] = 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]

Posted: **Sun Oct 03, 2004 3:28 pm**

by **dumb dan**

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:

Code: Select all

```
//while (!cin.eof()) {
//cin >> N;
while (cin >> N) {
```

I'm not even going to look at the rest of your code, but obviously something is wrong there too.

Good luck

### test data

Posted: **Sun Jun 26, 2005 9:31 pm**

by **Sedefcho**

Some sample data from an ACC program.

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.

### test data output

Posted: **Tue Jul 19, 2005 7:12 pm**

by **Callosciurus**

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!