I don’t understand how does this run in O(log MOD), it is from the section modular inverses:

```
int inv(int x) {
if (x <= 1) { return x; }
return MOD - MOD / x * inv(MOD % x) % MOD;
}
```

I don’t understand how does this run in O(log MOD), it is from the section modular inverses:

```
int inv(int x) {
if (x <= 1) { return x; }
return MOD - MOD / x * inv(MOD % x) % MOD;
}
```

Idk (maybe it does, but idk how to prove it).

Because it takes \mathcal{O}(\log p) time to compute a modular inverse modulo p,

I think this is referring to the method that uses exponentiation. Feel free to submit the contact form if you want the module to be clarified.

1 Like

Note that a way to modify this code so that it definitely runs in O(\log \text{MOD}) time is to have `x`

reduce to `min(MOD % x, x - MOD % x)`

. This way, `x`

reduces by at least a factor of 2 every time.

1 Like

I don’t think that, setting it to min(MOD % x, x-MOD%x) works.