here in that problem. After looking at my code ...

... I can give you the following information.

(x = 996600, y = 1004791, z = 1415209 ) is the last primitive

triple I have pregenerated. I have 245217 primitive ones in

total ( maybe the last several ones are useless ).

Anway. Now to the point. How do I calculate the second answer ?

Well, I simply do this. I assume first the answer is N ( this means

I include them all ). In the code below this is reflected with the line:

Code: Select all

`count = N;`

Well, I will just post then the relevant piece of my code:

My explanations are then below.

Code: Select all

```
count = N;
for (NAT i=0; i<cnt_prim_triples; i++){
xx = x_prim[i];
yy = y_prim[i];
zz = z_prim[i];
// if (xx>N) break;
k = 1;
while (k*zz<=N){
NAT x0 = k*xx;
NAT y0 = k*yy;
NAT z0 = k*zz;
if (!is_there[x0]){
is_there[x0] = 1;
count--;
}
if (!is_there[y0]){
is_there[y0] = 1;
count--;
}
if (!is_there[z0]){
is_there[z0] = 1;
count--;
}
k++;
}
}
```

1) cnt_prim_triples = 245217 as I have already said

2) is_there[] is just an array of 1000001 integers ( flags ),

**which prior to this cycle I set all to a zero value**

3) x_prim , y_prim, z_prim are the primitive triples ,

I have already pregenerated.

Note: I store my primitive triples in the following

order x_prim

*< y_prim*

*< z_prim**. But it is not always the case*

that x_prim[i+1] > x_primthat x_prim[i+1] > x_prim

*. Anyway, these are now just details.*

These two numbers are

and they are also

So actually why do we have the number 2 as second output for N=2,...5

The reason is that the count 2 corresponds to the numbers 1 and 2

( see my definition above )

Why are the answers for 6 and 7 -> 3 and 4 respectively ?

Well, if you follow the definition above you will see that N = 6 is really

part of the triple (2*3, 2*4, 2*5) BUT the biggest element in that

triple Z = ( 2*5 ) is not >= N = 6. So 6 is not counted as an element

of some triple.

Same happens with N=7. I mean 7 is part of the tripple

(7,24,25) BUT the biggest element here Z = 25 is not >= 7. So 7 is

not counted as an element of some triple.

That is the interpretation the Judge expects from us. I agree it does

not fully match to what is written in the problem statement.

Hope this helps.These two numbers are

1. not part of any of our pregenerated triples

1. not part of any of our pregenerated triples

and they are also

**2. not part ot any triple of the form (k*x,k*y,k*z),**

where x,y,z is some of our pregenerated primitive

triples , k>=2 and k*z <= N.

where x,y,z is some of our pregenerated primitive

triples , k>=2 and k*z <= N.

So actually why do we have the number 2 as second output for N=2,...5

The reason is that the count 2 corresponds to the numbers 1 and 2

( see my definition above )

Why are the answers for 6 and 7 -> 3 and 4 respectively ?

Well, if you follow the definition above you will see that N = 6 is really

part of the triple (2*3, 2*4, 2*5) BUT the biggest element in that

triple Z = ( 2*5 ) is not >= N = 6. So 6 is not counted as an element

of some triple.

Same happens with N=7. I mean 7 is part of the tripple

(7,24,25) BUT the biggest element here Z = 25 is not >= 7. So 7 is

not counted as an element of some triple.

That is the interpretation the Judge expects from us. I agree it does

not fully match to what is written in the problem statement.

Hope this helps.