Page 1 of 1
10214 - Trees in a Wood.
Posted: Tue Dec 18, 2001 8:11 am
by Hehe
I find this problem quite interesting,
but I haven't found a very good solution.
peng du, can you explain me the amazing 0.08 sec, 64K solution?
10214
Posted: Tue Sep 17, 2002 11:25 am
by cyfra
Hi!
I have a problem with this task..
Are there any tricks in the input ??
Could anyone who get AC answer my inputs ??
100 100
12 1324
1 10000
213 432
10 1000000
Thanx in advance
10214 - Trees In a Wood
Posted: Fri Oct 03, 2003 2:35 pm
by hujialie
Could anyone describe a good algorithm?
I solved this problem using too much memory(16000K),
just pre-treat it;so I want to make some improvement.
I know that computing Euler function may simplify it,
but how?
Thanks.
10214
Posted: Tue Apr 27, 2004 2:16 pm
by runa
hi all
plz any one help me to solve this problem 10214 .
the numbers which r relatively prime to n will be seen from origin.
& i can find it from Euler funtion formula .
F(n) = n * (1 - 1/p1) * (1 - 1/ p2) * ....*(1- 1 /pk)
but i can find it when x & y r equal . if x > y || y > x
then some values have to ignore . for example if x = 3 && y = 7
then we cannot count (4, 7), (7, 4), (5, 7), (7, 5), (6, 7), (7,6)
so how can i solve it ?
Posted: Wed Jul 07, 2004 6:52 pm
by abishek
my AC program gives the following output
0.6027723
0.5972457
0.6667111
0.6078071
0.5927436
for your input
simple tricks will be to try when trees that are on the boundary are not visible
and for various a or b=1
al the best
bye
abi
Posted: Wed Jul 07, 2004 6:54 pm
by abishek
just because it is given in the input like that you must now think that the answer is just the numbers less than a and b with gcd(a,b)==1. there is a solution that uses this idea of f inding
the no. numbers less than b with gcd()=1 with some other number
just think through the following..
why would you ever need to reject some point (x,y)
i hope it takes you closer to the answer
bye
abi