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!