逆元

参考于此篇博客:https://www.cnblogs.com/kongbursi-2292702937/p/10582258.html

逆元定义:

对于a*b≡1(mod m),b是a在模m下a的逆元。

首先对于同余符号≡,如 a≡b%m 表示的意思是a%m=b%m,a、b模m后余数相同。

逆元可以看作一个数的倒数 c * b≡1(mod m)(b为c的逆元)
可得(a/c)%m=(a*b)%m
推导过程:(a/c)%m=(a/c)*1%m=(a/c) * c * b%m=(a * b)%m

由费马小定理:a、m是互质的正整数,有a^(m-1)≡1(mod m)
可得:a的逆元为:a^(m-2)
推导过程:a^(m-1)≡1(mod m)=a*a^(m-2)≡1(mod m),由逆元定义可得 a逆元=a^(m-2)
其实就是转变为通过快速幂找到逆元。

快速幂板子(Mod还要自己定义个全局变量)

ll qpow(ll a, ll b) {
   
	ll ans = 1, base = a;
	while (b) {
   
		if (b & 1) ans = ans * base % Mod;
		base = base * base % Mod;
		b >>= 1;
	}
	return ans;
}

逆元常运用于组合数:https://blog.csdn.net/asbbv/article/details/111321575

全部评论

相关推荐

点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务