学习笔记：快速幂、逆元

首先说一下取模的运算：

$\left(a+b\right)\%mod=\left(a\%mod+b\%mod\right)\%mod$ $\left(a-b\right)\%mod=\left(a\%mod-b\%mod+mod\right)\%mod$ $\left(a\ast b\right)\%mod=\left(a\%mod\ast b\%mod\right)\%mod$ 但是： $\left(a/b\right)\%p=\left(a\%p/b\%p\right)\%p$ 是错误的！！！等式不成立。 例如：$\left(6/2\right)\%2=1$ , $\left(6\%2/3\%2\right)\%2=0$

切入正题：逆元

$\left(a\ast x\right)\%p=1$, $x$ 就等于$\frac{1}{a}$吗，不一定，因为这里还有条件呢：$mod$ p,所以在这个条件下$x$叫做$a$关于$p$的逆元,比如：$(2\ast 3)\%5=1$,那么$3$关于$5$的逆元就是$2$或者说$2$关于$5$的逆元就是$3$，$2$和$3$关于$5$互为逆元。

怎么求逆元呢？ 费马小定理：$a^{p-1}\%p=1$($a$与$p$互质)， 两边同时除$a$得：$a^{p-2}\%p=\frac{1}{a}$，大功告成，$a$关于$p$的逆元就是$a^{p-2}\%p$，记为$inv(a)=a^{p-2}\%p$.

再回到刚开始的问题：如何求$(a/b)\%p$，应用刚才的费马小定理即转换为$(a\ast inv(b))\%p$再转化为$(a\%p\ast inv(b)\%p)\%p$，就完全转换成好算的乘法了，所以就求出$inv(b)=b^{p-2}\%p$就可以算出结果了。

$b^{p-2}$就可以用快速幂解决，复杂度$O(logn)$ 下面代码求$a^b\%mod$

long long POW(long long a,long long b,long long mod) { long long base = a,ans=1; while(b) { if(b&1) ans=(ans*base)%mod; base=(base*base)%mod; b>>=1; } return ans; }

再来个例题：hdu 1576 A/B

Problem Description

要求(A/B)