线性求逆元

简介

逆元，简单的来说就是 a∗b≡1(modp) ，那么b就是a关于p的逆元。 正常的来说用扩展欧几里得来做。复杂度不是线性的。 但是如果所有的i≤p，有一个线性求逆元的方法。 正常的来说

方法

因为 i≤p ，所以考虑用i来表示p，并要求表示出来的所有数都能用p和i表示。 设 p=ki+b，k=⌊pi⌋，l=pmodi 那么 ki+b≡0(modp) 因为要求的是 i−1 ，所以需要把 i−1 独立起来，所以我们等式两边同时乘以 i−1b−1 那么式子就可以变成 kb−1+i−1≡0 然后把可以求得i的逆元的数放到右边去。 i−1≡−k∗b−1 然后再把k和b用p来表示。 i−1≡−⌊pi⌋∗(pmodi)−1 设数组a[i]表示i的逆元 那么由上面的式子可以知道： a[i]=−⌊pi⌋∗a[pmodi]−1 所以 a[i]≡−⌊pi⌋∗a[pmodi]−1 把上面的东西优化一下 因为系数带p的在mod p意义下都视为0 a[i]≡−⌊pi⌋∗a[pmodi]−1+p∗a[pmodi]−1 所以 a[i]≡(p−⌊pi⌋)∗a[pmodi]−1 为了方便记忆，式子可以改为 a[i]≡(p−⌊pi⌋)∗a[p−⌊pi⌋∗i]−1