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

capella
New poster
Posts: 5
Joined: Thu Jun 19, 2003 6:22 am

### Can you tell me what should I do with this?

I'm sorry that I don't have much concept about efficiency. I wonder how it runs on my computer. But if I don't do like this, how can I deal with the seen array? It seem the formula a*a-b*b,2*a*b,a*a+b*b doesn't generate all triple, such as 9,12,15.
Thanks.

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wroc&#322;aw
what is output for 1000000 ?
what is the second number in output ?
i don't understand this in that problem.
how compute this second value ?

my output's for samples:
1 4
4 10
16 36
or
1 4
4 8
16 23
and
there are all triples
3 4 5
6 8 10
9 12 15
12 16 20
15 20 25
18 24 30? - 30>25 is this real triple?
8 15 17
5 12 13
10 24 26 - 26>25 is this real triple?
7 24 25

please help

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wroc&#322;aw
hello
why there is triple: 10,24,26 ?
26 is larger then 25 and there is "x, y, and z are constrained to be positive integers less than or equal to N."
maybe i'm wrong because i learn english only one year. so if somebody coulds explain me.
thanks

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

### Triples in the second example

Here are the triples that count (x, y, and z are ALL less than or equal to 25)(( I have them separated into groups that are multiples))

3,4,5
6,8,10
9,12,15
12,16,20
15,20,25

8,15,17

5,12,13

7,24,25

Since there are four such groups, the first number in the output should be 4

Now, take a look at all the numbers between 1 and 25 that are in any group:

{3,4,5,6,7,8,9,10,12,13,15,16,17,20,24,25}

(There are 16 numbers in that set)

Finally, look at the set of numbers not included:

{1,2,11,14,18,19,21,22,23}

Since there are 9 numbers, the second number in the output should be 9.

capella
New poster
Posts: 5
Joined: Thu Jun 19, 2003 6:22 am

### the output

hi Rav if you are looking for the output for n=1000000 here is another post containing this

http://online-judge.uva.es/board/viewtopic.php?t=2293

But can anyone answer my previous question?
Now I have changed my code as:
[c]
up=sqrt(n/2);
for(int b=1;b<=up;b++)
for(int a=b+1;(z=a*a+b*b)<=n;a++){
x=a*a-b*b;
y=2*a*b;
if(cop(x,y) && cop(x,z) && cop(y,z)){
ct++;
for(int i=1;z*i<=n;i++){
seen[x*i]=1;
seen[y*i]=1;
seen[z*i]=1;
}
}
}
[/c]
now it executes the inefficient segment only if it has found a coprime triple. Is this still O(n^2)? My result is still Time Limit Exceeded. What is the efficient algorithm for counting the numbers not belonging to any triple? Thanks! Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wroc&#322;aw
hi
you could use bool table and i thing this be all. my alghoritm is same and work well .

if(cop(x,y) && cop(x,z) && cop(y,z))
{
for(i=1;z*i<=n;i++)
{
seen[x*i]=1;
seen[y*i]=1;
seen[z*i]=1;
}
ct++;
}
and i thing you can change there your code. i dont sure that bie the same result.
and how to compute this second number
and how many triples (all triples) is for sample 25.
11 ? or 8 ?

capella
New poster
Posts: 5
Joined: Thu Jun 19, 2003 6:22 am

### Thanks Ryan Pai!

There r 8 triples for n=25.

Thanks so much for Ryan Pai's message just now!!! Yes my problem is indeed that I should use % in cop but not substracting and substracting. I got AC finally!!! So happy , though it takes 8 seconds El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands
Hi Ryan,

Wow, without your explanation I would never have figured out this algorithm. I guess my number theory is a bit rusty... I had the same problem with prob 104 where the solution is to use Floyd-Warshall... I hadn't heard of it I think the reason for my rustiness is that the appz I develop for my work are not specifically math oriented (they are more data and functionality oriented).

Thanks a lot for the help.

palespower
New poster
Posts: 6
Joined: Fri Aug 15, 2003 9:12 am
Hi guys ... I've done the Fermat vs. Pythogoras problem using the following algorithm :
I found that for a any triple x^2+y^2 = z^2 there applies the following...
x^2 = z + (z-1) + (z-1) + (z-2)......+(y+1) + (y);
for example for the triple (3, 4, 5);
3^2 = 5 + 4;
for the triple (7, 24, 25);
49 = 25 + 24;

for the triple(6, 8, 10):
36 = 10 + 9 + 9 + 8;

so what I did is I have two loops to get two numbers z, y.. and a recursive function to get x;....
but I get a Run time Error...
This is the message:
Your program has died with signal 8 (SIGFPE). Meaning:

Floating point exception

Before crash, it ran during 0.027 seconds.

--
can anybody tell me what is wrong here .. here's my code...
[c]/* Maan Musleh
* Fermat vs. Pythogoras
* http://acm.uva.es/p/v1/106.html
*/

#include<stdio.h>
#include<math.h>

long int triple;

long int generate (long int y, long int z) {
long int x_square;
if (y == z) return 0;
x_square = z + z-1 + generate(y,z-1);
return (x_square);
}

int find (long int xx, long int y) {
long int x, i, j;
x = 0;
for (i = y; i >= 2 ; i--) {
j = i*i;
if ((xx/j == 1)&&(xx%j == 0)) {
x = i;
break;
}
}
return (x);
}

int check(x,y,z)
long int x,y,z;
{
long int p,u;
triple[x-1] = 0;
triple[y-1] = 0;
triple[z-1] = 0;
for (p =2; p<=z/2; p++) {
u=0;
if ((x%p==0)&&(y%p==0)&&(z%p==0)) {
u =1;
break;
}
}
return u;
}

main () {
long int i, j, k, mm, h, N;
int a;
long int count;
long int kk;
int count_triple;
while (scanf("%d\n",&N)==1) {
a =1;
k = 1;
count = 0; count_triple = 0;
for (i = 0; i<N; i++) {
triple = i+1;
}

for (i = N; i >= 5; i--) {
for (j = i-1; j >= 4 ; j--) {
kk = generate(j, i);
k = find(kk, j);
if ((k > 0)&&(k<j)){
a = check(k, j, i);
if (a == 0) {
count_triple++;
}
}

}
}

for (h = 0; h < N; h++) {
if (triple[h]!=0) count++;
}
printf("%d %d\n", count_triple, count);
}
}
[/c]

Plz help me in this

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

### hmm...

I dont even see any floating point arthematics in your code....

And I would like to ask how home the heading of your check function is little different then the normal declaration?

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
If I'm correct fpe can also occur on division by zero, and the code does include division. Better use debugger Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

palespower
New poster
Posts: 6
Joined: Fri Aug 15, 2003 9:12 am
I'm sorry I didn't understand ur question... can u explain it again....

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
what I meant to say was that SIGFPE 8 can happen on division by zero, ie you want to divide some integer by 0. I haven't run your code and I haven't debugged it but I saw division there. So, I wanted to let you know that the crash might be due to division by zero.

For this problem you can test any input. Try generating input file with integers from 1 to 1000000, one per line. If your program crashes, try to find the crashing case. Use debugger, trace through your code. That's the best suggestion I can give you without digging thouroughly thhroug your code.

And if really necessary, I can send you the source for testing your answers (just because this particular my first solution will get TLE with current time limit )

All the best,
Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
true, there is a part where u have j=i*i and xx/j, xx%j. i is can be as big as y, which can be as big as N-1, which can be as big as 10^6, so j can be as big as (10^6)^2 = 10^12, but long can only take 10^10...so that cause unknown denomanator, which might be 0 is u're unlucky.

look at the check function, the function heading is abnormal, is that just a mistake of copy and pasting?

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
it's not abnormal - it's unusual and it's just old it's an older way of defining c functions and it's arguments.

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.