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_prim . Anyway, these are now just details.
These two numbers are
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.
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.