Please, help with this test. I am always getting WA on it.
I did 2 assumptions:
1. If after any iteration the radius becomes irrational - then the answer will be irrational too.
2. The numerator and denominator of resulting fraction both don't exceed 2^64.
Are these assumptions wrong? If so, please, give me some useful tests. The one interesting test I found is:
1 1 30 34785346
3131185849/1170753394542713625
But it doesn't help me much...

Edited by author 04.02.2011 02:56

The 1st assumption is right.
The 2nd one seems to be wrong. I can't say exactly if the result always fits in int64, but temporary (or itermediate) calculations exceed 2^64 for sure.

Answer to your test is wrong. In this test the denominators of intermediate fractions (before reduction) exceed 2^64.

My AC program answer:
1/6265197409

Oh, thanks, now I understood why it gets WA. Now my program gives correct answer to this test (I optimized it a little bit), but I found several tests with the same problem. It is interesting for me to solve it without BigInteger, I guess, there exists such solution for this problem.

After a lot of tries I gave up :(
AC now, but with big numbers.

Edited by author 07.02.2011 23:02

I got Wa22(ac 1-21) under positions:
r1*r2!=k*k-"irrational";(BUT IF i>min and i<MAX ONLY!)
else
1/sqrt(r)=a/sqrt(r1)+b/sqrt(r2);
a,b- recursion f(n,2i)=f(n-1,i),f(n,2i+1)=f(n-1,i)+f(n-1,i+1)
All- __int64
AC now:
a,b<=30- by induction.
int- is enought, nor __int64, nor BigInteger

Edited by author 27.02.2011 12:18

My mistake was: __int64 needed.
a+b<=2^30

Что бы не было переполнения вы могли сделать следующие : Представить r1 и r2 таким образом
r1 = A / B ^ 2
r2 = A / C ^ 2
Где А = r1 * r2 / gcd(r1, r2);
Отсюда найдете B и C.
Теперь в чем прелесть такого представления:
Вы наверное вывели формулу r3 = (r1 * r2 ) / (r1 + r2 + 2 * sqrt(r1, r2) );
Так вот если будете подставлять то получите r3 = A / ( B + C) ^ 2
т.е числитель не меняется а вот знаменатель будет меняться но не быстро !