Hi!↵
↵
I was hoping someone could help me understand how this bit of code works written by [saeed_odak](https://codeforces.net/profile/saeed_odak) in this submission to 1117E : [code](https://codeforces.net/contest/1117/submission/50126643): ↵
↵
- `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](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) itself details the algorithm quite well. Looks like I posted prematurely without doing enough searching on my part.↵
↵
Sorry!
↵
I was hoping someone could help me understand how this bit of code works written by [saeed_odak](https://codeforces.net/profile/saeed_odak) in this submission to 1117E : [code](https://codeforces.net/contest/1117/submission/50126643): ↵
↵
- `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](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) itself details the algorithm quite well. Looks like I posted prematurely without doing enough searching on my part.↵
↵
Sorry!
