数学逆元计算

  • 开发
  • 15

定义ax_{} mod_{}p\equiv 1，即是有a=x{_{}}^{-1}（在mod p 的意义下），也就是求倒数

根据定义，则有\frac{a}{b} mod p=a*inv(b)，b的逆元就是b^{​{_{}}^{-1}}

所以得出第一个计算式

\frac{a}{b}=a*inv[b]

求_{n}^{m}\textrm{C}，可以快速计算较大情况：

inv[i]表示i!的逆元的值，则有：

fac[0]=1;
for(int i=1;i<=N;i++){
	fac[i]=fac[i-1]*i%mod;
	inv[i]=invv(fac[i]);
}

那么求得\frac{n!}{m!(n-m)!}的公式为fac[n]*inv[m]*inv[n-m]

求逆元的证明

inv[p]=p{_{}}^{mod-2}

由费马小定理，得a^{p-1}\equiv 1，此时的p为质数

联立inv[p]=p^{-1}得证

阅读全部

相关推荐

  2. 【算法】数论---乘法逆元

    2024-03-30 08:30:04       22 阅读

  3. 【算法基础 & 数学】快速幂求逆元（逆元、扩展欧几里得定理、小费马定理）

    2024-03-30 08:30:04       34 阅读

  7. C++求逆元、分数取模

    2024-03-30 08:30:04       33 阅读

  8. 快速幂求逆元-C语言

    2024-03-30 08:30:04       21 阅读

  9. 【二进制计算，逆序，每位求和】

    2024-03-30 08:30:04       20 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-03-30 08:30:04       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-03-30 08:30:04       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-03-30 08:30:04       19 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-03-30 08:30:04       20 阅读

热门阅读

  2. 【强化学习概念01】什么是 Q-Learning：了解 Q-Learning 的最佳指南

    2024-03-30 08:30:04       13 阅读

  3. RTSP服务端的响应格式

    2024-03-30 08:30:04       14 阅读

  5. 各类Springboot管理系统源码获取

    2024-03-30 08:30:04       15 阅读

  6. 5.98 BCC工具之biotop.py解读

    2024-03-30 08:30:04       12 阅读

  8. 【使用 PyQt6-第02章】 创建信号、槽和事件

    2024-03-30 08:30:04       14 阅读

  9. 5.97 BCC工具之biolatency.py解读

    2024-03-30 08:30:04       15 阅读

  10. Mac更换JDK版本

    2024-03-30 08:30:04       16 阅读

  11. gateway 分发时若两个服务的路由地址一样，怎么指定访问想要的服务下的地址

    2024-03-30 08:30:04       17 阅读

  14. 每天一个数据分析题（二百四十一）

    2024-03-30 08:30:04       22 阅读

  19. Python爬虫之数据的存储

    2024-03-30 08:30:04       15 阅读

  21. C++ 让类只在堆或栈上分配

    2024-03-30 08:30:04       21 阅读

  24. 搭建vite+vue3项目时遇到的问题

    2024-03-30 08:30:04       19 阅读

  29. DG库怎样释放bigfile类型临时数据文件的空间

    2024-03-30 08:30:04       16 阅读