1

$p$ 是模数。

inv[1] = 1;
for(int i = 2; i < p; ++ i)
    inv[i] = (p - p / i) * inv[p % i] % p;

这种求逆元的方法的限制条件，是否仅有存在逆元。

2

改写问题 1 的代码得到单点求逆元：$a$ 是要求逆元的数，$m$ 是模数。

LL solve(LL a, LL m) {
  if (a == 1) return 1;
  return (m - m / a) * solve(m % a, m) % m;
}

这玩意的时间复杂度如何？目测 $a = m / 2$ 左右的时候，$a$ 每次减一，可以卡到线性，但是随机了三个 1e7 质数发现最大递归次数只有至多 40 次。这是为什么？还是说这个东西的复杂度和求 $\gcd$ 一样？

3

https://judge.yosupo.jp/submission/190274 开头

struct LMont_32{
    u32 M,M2,niv,R,R2;
    LMont_32()=default;
    LMont_32(u32 m):M{m},M2{m*2},niv{2+m},R{-m%m},R2((-u64(m))%m){
        for(int i=0;i<4;++i){niv*=2+m*niv;}
    }
  // ...

这里实现了一个蒙哥马利约减，$niv$ 应当是 $-m^{-1}\bmod 2^{32}$，请问 for(int i=0;i<4;++i){niv*=2+m*niv;} 背后的原理是什么？