Hi! Modular inverses are used in the solutions to a lot of number theory problems, such as 622F - The Sum of the k-th Powers from the latest educational round. I want to share a one-liner (essentially) that computes modular inverse with the same complexity as the exteneded Euclidean algorithm (a and b are supposed to be positive co-prime integers, and inv(a,b) is the inverse of a modulo b, lying between 1 and b):

```
long long inv(long long a, long long b){
return 1<a ? b - inv(b%a,a)*b/a : 1;
}
```

The idea behind the code is that to compute inv(a,b), we find x such that and , and then return `x/a`

. To find x, we can write *x* = *yb* + 1 and solve for y by recursively computing inv(b,a). (Actually `inv(b%a,a)`

)

This isn't the fastest method if you're worried about performance, and you will probably get overflow if a*b doesn't fit inside a long long. But I think it's neat.