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.
106 - Fermat vs. Pythagoras
Moderator: Board moderators
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
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
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.
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.
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!
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!
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 ?
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 ?
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 
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.
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:
[c]/* Maan Musleh
* Fermat vs. Pythogoras
* http://acm.uva.es/p/v1/106.html
*/
#include<stdio.h>
#include<math.h>
long int triple[1000000];
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
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:
can anybody tell me what is wrong here .. here's my code...Your program has died with signal 8 (SIGFPE). Meaning:
Floating point exception
Before crash, it ran during 0.027 seconds.
--
[c]/* Maan Musleh
* Fermat vs. Pythogoras
* http://acm.uva.es/p/v1/106.html
*/
#include<stdio.h>
#include<math.h>
long int triple[1000000];
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
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?
And I would like to ask how home the heading of your check function is little different then the normal declaration?
If I'm correct fpe can also occur on division by zero, and the code does include division. Better use debugger 
Ivor
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
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
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.
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?
look at the check function, the function heading is abnormal, is that just a mistake of copy and pasting?
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
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.