OJ Board

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.

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

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

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.

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!

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 ?

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

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.

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[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 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?

If I'm correct fpe can also occur on division by zero, and the code does include division. Better use debugger

Ivor

I'm sorry I didn't understand ur question... can u explain it again....

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

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?

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