Resistance - how to fix this solution?

Hello coders,

I’d like to ask if it is possible to fix this solution for resistance problem:

I realized that circuit is recursive (see the picture):


In the picture there is green R2 and red R3 in R4.

This can be described with formulae:

1/R_n = 1 + 1/(1 + R_n-1)

if I use

R_n = a_n / b_n, R_n-1 = a_n-1 / b_n-1

I’m getting

alt text

using formulae for R_n I’m getting

alt text

so far so good. When I used BigDecimal in Java R_100 is calculated well, so formulae seems to be ok, but BigDecimals are to slow to get 200.000th. When I use longs and use modulo k in each I’m getting wrong results from n = 9 :frowning:

UPD: I found, that when I skip finding of gcd it is ok, but is there a way to use gcd ?(because without tutorial I won’t know, that these numbers are Fibonacci numbers and gcd is always 1)

public static void solve( final int n, final int mod ) {
    final long[] a = new long[ n + 1 ];
    final long[] b = new long[ n + 1 ];
    a[1] = 1;
    b[1] = 1;
    for ( int i = 2; i <= n; i++ ) {
        a[i] = ( a[i - 1] + b[i - 1] ) % mod;
        b[i] = ( a[i - 1] + 2 * b[i - 1] ) % mod;
        // long g = gcd(a[i], b[i]);
        // a[i] /= g;
        // b[i] /= g;
    System.out.printf( "%d/%d\n", a[n], b[n] );

don’t use BigDecimal,do with the starting formula and mod your result everytime.

1 Like

getting the modulo everytime won’t get the correct result, as the fraction will be wrongly modified. before using fibonacci, i had the same idea than you, betlista, but it appears that, even with using gcd at each step, the numbers are too big to fit in integers. there seem to be no other way if you don’t want to handle such numbers.

In fact my problem was with gcd(), on moduled a[i] and b[i] gcd is not always 1 :frowning: Is there a workaround for this when I do not find that I do not need to use gcd() in contest?

@cyberax in fact, modulo is ok, but gcd() doesn’t work well with modulo operation, see the code in updated question - it works, but the question is how to solve this without knowledge, that gcd is always 1…

you don’t need to use gcd if you use fibonacci numbers, as i said before. :slight_smile: