线性求逆元

前几天我的指导老师给了我一个提高组的考纲,看了看发现数论缺了一大块,一波补习学会(背过)了费马小定理的结论,然后根据结论开始求逆元

做的就是这个题

信心满满的提交然后挂了

然后跟随某个大佬学了学如何线性的求逆元(感觉别的大佬们讲的都好难懂)

然后我来再讲一遍(帮助理解)

首先我们要求i的逆元,我们定义为inv[i],现在定义k和t,ki+r线性求逆元0(mod p)

然后我们移个项:r线性求逆元-ki(mod p)

然后等式两边同时除以ri

就会变成:i分之1线性求逆元-k分之r(mod p)

我们知道i分之1等于i的逆元

还知道r分之1等于r的逆元

那么整理一下可知:inv[i]线性求逆元-k*inv[r](mod p)

而且我们还知道r是小于i的,所以r=p%i

再整理一下:inv[i]线性求逆元-k*inv[p%i](mod p)

我们还知道k*i+r线性求逆元0(mod p)

所以k就是p/i,然后我们根据c++里%的特点,再让他强行转正,加一个p

最后一次整理inv[i]=(p-p/i)*inv[p%i]%p

然后经过这一波分析,我们得到了公式:inv[i]=(p-p/i)*inv[p%i]%p

膜拜教会我的大佬,贴上原博客地址

上一篇:题解 LOJ #2527. 「HAOI2018」染色


下一篇:P5431 【模板】乘法逆元2(小学数学题,毒瘤鱼,卡常之王yyds)