笔记——奇怪的逆元

· · 个人记录

CF 看到的，写个笔记记录下，挺强的。

现在要求 a\bmod b 的逆元，不妨我们已经求出了 b\bmod a 的逆元 w。

那么记 \frac{bw-1}{a}=q，则有 b|aq+1，换句话说 -q 就是我们要求的逆元。

然后搬运个 CF 原文 的代码吧。

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

好方便，但是我选择 atcoder lib。