OJ Board

I am getting WA for this problem. Can anyone tell me what are the correct output for 6, 8 & 10? I get 290, 530 & 1010 respectively. Are these results right?

Nafi

My results are wrong for N = 8 & 10. I have found a mistake in my derivation.

Nafi

my prog(wich judge think wrong) for:
2
4
6
8
10
100
1000
10000
100000
200000
0
return :
Crystal 1: 26
Crystal 2: 98
Crystal 3: 290
Crystal 4: 578
Crystal 5: 1154
Crystal 6: 854786
Crystal 7: 834185090
Crystal 8: 832136021570
Crystal 9: 831930692993858
Crystal 10: 6655340768473154

It's correct? wich case wrong?pls help
PS. in sol I use eratosfen sieve

Strange. Your output is correct.

now all ok (I get accepted)
but i think exist some bug in fpc
cose my 1 try(wrong) use var r:comp; and writeln(r:0:0)
and 2 try(accepted) use var r:int64; and writeln(r);

in home i use:
for 1try bp(turbo/borland pascal)
for 2 try dcc( delphi )
for all value they get same result
but on judge under fpc they difrent

PS.HELLO ADMIN! AM I right?

If my information is correct, the type Comp is a 64 bit signed integer type that is handled by the Floating Point Unit of an Intel type processor, instead of being implemented as a true 64 bit integer type, so it might be possible that it suffers from rounding errors. (The type is not defined for other than Intel architectures).
I think it is safest to use Int64 (signed) or QWord (unsigned) if you use 64 bit integers. They are either directly handled by the CPU (Athlon 64) or split by the compiler into two 32 bit integers. I think the judge runs on a 32 bits machine, so the latter might be the case.

I need a hint to solve this problem (I will be very happy if a complete illustration is posted).

(Assuming you know about Euler's Phi function.)

My approach starts from thinking about a two dimensional version of Phi function.
Let A(n) be | { (x,y) : 1<=x,y<=n and gcd(x,y,n)=1 } |
What's A(n) when n is prime? power of prime?
What's A(ab) if a and b are co-prime?

Then the final solution could be built up from this function A.

I used principle of inclusion-exclusion.

To solve 3D problem (x>0, y>0, z>0) I do this:

Let f(k) be the number points (x,y,z) such that 0<x<=N, 0<y<=N, 0<z<=N and such that x, y, and z are multiples of k.

f(k) = (N/k)*(N/k)*(N/k) (it's integer division)

First, let's count total number of points. It's f(1).

Now we have to subtract f(2) because gcd for those points is not 1 (it is at least 2), so those points are not valid.
Also we subtract f(3), f(5), f(7)... because of same reason...
But then we subtracted points like (6,6,6) twice (once with f(2) and once with f(3)). So we have to add them once more. So we add f(2*3), f(2*5), f(3*5)...
And so on...

So we end up with something like this:
f(1) - f(2) - f(3) - f(5) - f(7) - ... + f(2*3) + f(2*5) + f(3*5) + ... - f(2*3*5) - f(2*3*7)...

Obviously, f(k)=0 for k > N, so there will be at most N (nonzero) terms to add (subtract).


You can use the same approach to solve 2D problem (to count the number of points like (x,y,0), (x,0,z) and (0,y,z) )

1. cho can you explain?(your sol very fast-0.064sec)
2. my sol is(0.152sec more then 2 time slow ) :
w=(2*i+1)^3
s=w-w[i-1];
p=s-sum(p[j]| i mod j=0, 0<j<i);
r=sum(p,1..i);
where w- all atoms in cube 2i
s-new atoms (|x| or |y| or |z| ==i)
p-atoms in level i from wich can view center (0,0,0) or as same gsd(x,y,z)==1
r[i] - that us ask

Thank you very much Mr. Cho and Mr. Kalinov for your explanations.

The bottle neck of my algorithm is the sieve, afterwards, everything can be done in linear time. Since our approaches are different, it's not surprised that there is a constant factor difference in the running times.

Mr. Kalinov. Can you describe how to make this effitiently?
(I am sorry for annoyance, but I am not very good at these tricks of discrete math)

Cho wrote:The bottle neck of my algorithm is the sieve,

my too (for j:=2 to m div i do dec(p[i*j],p);

Cho wrote: afterwards, everything can be done in linear time.

yep!

Cho wrote:Since our approaches are different, it's not surprised that there is a constant factor difference in the running times.

I think not so dif.
Cho can you more detail about your sol
ps. by the way if s:=i than p -euler phi function

1. Run sieve so that factor[n] store the max prime factor of n
2. Compute all phi[n] by making use of factor[n], O(n)
3. Compute all A[n] by making use of factor[n], O(n)
4. Compute all sumphi[n] to be phi[1]+...+phi[n], O(n)
5. Compute all sumA[n] to be A[1]+...+A[n], O(n)
6. Finally, for each query, the answer can be computed in O(1).
So, the bottle neck is phase 1.

>> p=s-sum(p[j]| i mod j=0, 0<j<i);
Is this part O(n sqrt(n))?