January 21, 2021

# Rational Resistance - 343 A

https://codeforces.com/problemset/problem/343/A

## Simplified Problem Statement

With the standard law of resistance in a circuit (serial is `r1+r2` and parallel is `1/(1/r1 + 1/r2)`), determine the smallest possible number of `unit` resistor to create an equivalent resistance of irreducible fraction `a/b`.

## Constraint

`a, b <= 10^18`

## Analysis

For very large `a`, it doesn’t matter that much that the value is large because what we need is to only write the value. Maybe if we can simplify the question to if we can create `1/b`? This is easier since we need to have `b` resistor, assign them in parallel. Then get `a` of this, hence we can get an assignment of `a/b` with `a*b` number of resistor, which certainly is not the optimal (minimum) way.

Let us take an example first I guess. I think using a notation would help. + For serial, | for parallel - `1/2` is o|o - `2/3` can be created by `(o|o|o) + (o|o|o)`, or by `o|o + o|o|o|o|o|o`, or by `(o+o) | o`.

I think for if `a/b > 1`, having a series of `x` resistor such that the `a/b - x < 1` is the best way to do? It might not always be true. For example if we have `4/3`, not sure if `1 + 1/3` is better of `2/3 + 2/3` is better. Although in that specific case, `1 + 1/3` use 4 resistor, meanwhile `2/3 + 2/3` uses 6.

Let us maybe see the other example from the test case, which is `199/200`. The test case provided the answer as `200`. We will need `1/(200/199)`. Which is available by? Let’s look at the `200/199`, it is `1/199 + 1`. What if I want `199/201`? Surely there’s a better way then doing `1/199 + 1/199 + 1`.

Stop stop! I see something insightful. If we flip `a/b`, all the operation will flip and will give the same result. E.g.: - `2/3` is `(o+o) | o` - `3/2` is `(o|o) + o`. - `199/200` is `(o+o+...+o) | o` - `200/199` is `(o|o|...|o) + o`

Maybe I can think of the proof later, but this seems to be promising. In this case, what we can do is to keep flipping such that when the value of the equation is > 1, we reduce the numerator with the denumerator. I think we can code this.

## Implementation

``````int main() {
setIO();
ll a; ll b; re(a, b);
ll count = 0;
while(a != 0 && b != 0){
if(a < b){
ll tmp = b;
b = a; a = tmp;
}
count += a/b;
a %= b;
}
ps(count);
// you should actually read the stuff at the bottom
}
``````

Accepted yey!