Hi!

I was hoping someone could help me understand how this bit of code works written by saeed_odak in this submission to 1117E : code:

`int mul_inv(int a, int b) { //Returns multiplicative inverse of a wrt b`

`int b0 = b, t, q;`

`int x0 = 0, x1 = 1;`

`if (b == 1) return 1;`

`while (a > 1) {`

`q = a / b;`

`t = b, b = a % b, a = t;`

`t = x0, x0 = x1 - q * x0, x1 = t;`

`}`

`if (x1 < 0) x1 += b0;`

`return x1;`

`}`

``- I think understanding how to write an iterative GCD function that develops GCD coeffecients would be helpful to understand this piece of code, but I can't seem to come up with a way to do so and online searches only provide code and not good explanations.

Any help would be appreciated.

Thank you!

EDIT: Resolved. Looks like there were actually sources that explained that algorithm well that I missed. The wikipedia page Wikipedia itself details the algorithm quite well. Looks like I posted prematurely without doing enough searching on my part.

Sorry!

Auto comment: topic has been updated by grandesonnerie (previous revision, new revision, compare).I just want to add that the recursive version is much easier to understand and derive (in my opinion).

You can read about it here

Thanks for linking, the post was really helpful!