线性求逆元

• LLX123654 发布于
• 1287 收藏

说在前面 在某些组合数的计数问题中，经常会用到逆元，这里我们讲一下如何线性求出1到n在模p意义下的逆元，注意p为质数。 进入正题 假设我们当前要求a在模p意义下的逆元。 令p=ak+r,(0≤rak+r≡0(modp)ak+r≡0(modp)，然后恒等式变形，两边同时乘a−1×r−1a−1×r−1， 则有a−1+kr−1≡0(modp)a−1+kr−1≡0(modp)，移项 既得a...