数论 —— 快速幂与同余式定理 —— 逆元

• tudiu 发布于
• 961 收藏

【概述】 1.定义：若 ，a、b 互质，则称 x 为 a 的逆元，记为  2.同余模公式 3.应用：当题目要求对结果求 m 的模，且当过程需要计算  时，需要对  取模，即  ，有时 b 过于大，会出现爆精度的情况，所以需要变除法为乘法。 即：设 c 是 b 的逆元 则： 故： 即： 4.求解逆元方法 1）费马小定理 2）扩展欧几里德算法 3）线性求逆元 【费马小定理求...