10214 - Trees in a Wood.

[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?

[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

[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.

[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 ?

[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

[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