传送门：
http://www.2cto.com/kf/201401/272375.htm
新学的一个求逆元的方法：
inv[i] = ( MOD - MOD / i ) * inv[MOD%i] % MOD
证明：
设t = MOD / i , k = MOD % i
则有 t * i + k == 0 % MOD
有 -t * i == k % MOD
两边同时除以ik得到
-t * inv[k] == inv[i] % MOD
即
inv[i] == -MOD / i * inv[MOD%i]
即
inv[i] == ( MOD - MOD / i) * inv[MOD%i]
证毕
适用于MOD是质数的情况，能够O(n)时间求出1~n对模MOD的逆
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 cncqzxj 的文章《【数论】【逆元】【O(n)时间求出1~n对模MOD的逆元】》','https://www.xiaopingtou.net/article-55961.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}