11014  Make a Crystal
Moderator: Board moderators
11014  Make a Crystal
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
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
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
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?
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?

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
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 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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
(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 coprime?
Then the final solution could be built up from this function A.
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 coprime?
Then the final solution could be built up from this function A.
I used principle of inclusionexclusion.
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) )
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 fast0.064sec)
2. my sol is(0.152sec more then 2 time slow ) :
w=(2*i+1)^3
s=ww[i1];
p=ssum(p[j] i mod j=0, 0<j<i);
r=sum(p,1..i);
where w all atoms in cube 2i
snew atoms (x or y or z ==i)
patoms in level i from wich can view center (0,0,0) or as same gsd(x,y,z)==1
r[i]  that us ask
2. my sol is(0.152sec more then 2 time slow ) :
w=(2*i+1)^3
s=ww[i1];
p=ssum(p[j] i mod j=0, 0<j<i);
r=sum(p,1..i);
where w all atoms in cube 2i
snew atoms (x or y or z ==i)
patoms in level i from wich can view center (0,0,0) or as same gsd(x,y,z)==1
r[i]  that us ask
my too (for j:=2 to m div i do dec(p[i*j],p);Cho wrote:The bottle neck of my algorithm is the sieve,
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=ssum(p[j] i mod j=0, 0<j<i);
Is this part O(n sqrt(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=ssum(p[j] i mod j=0, 0<j<i);
Is this part O(n sqrt(n))?