如何作求模运算?

1.取模运算是什么意思?

取模运算是求两个数相除的余数。

取模运算(“Modulo Operation”)和取余运算(“Remainder Operation ”)概念重叠但不完全一致。

主要的区别在于对负整数进行除法运算时操作不同。

取模主要是用于计算机术语中。

取余则更多是数学概念。

2.如何做取模运算?

如果 % 两边的操作数都为正数,则结果为正数或零;

如果 % 两边的操作数都是负数,则结果为负数或零。

C99 以前,并没有规定如果操作数中有一方为负数,模除的结果会是什么。

C99 规定,如果 % 左边的操作数是正数,则模除的结果为正数或零;

如果 % 左边的操作数是负数,则模除的结果为负数或零。例如:

          15 % 2       // 余 1
          15 % -2      // 余 1
          -15 % 2      // 余 -1
          -15 % -2     // 余 -1

标准规定,如果 a 和 b 都是整数,则 a % b 可以用公式 a - (a / b) * b 算出。例如:

          -15 % 2 == -15 - (-15 / 2) * 2 == -15 - (-7) * 2 == -1

如果ax1(mop),且a与p互质(gcd(a,p)=1),则称a关于模p的乘法逆元为x。(不互质则乘法逆元不存在)

求逆元的四种方法:

什么是逆元?

逆元--即逆元素,是指一个可以取消另一给定元素运算的元素

也就是说,你对A做了某种操作,得到A',现在你又用某个神奇的力量对A'操作,然后使A'又回到了A,这个神奇的力量就叫A的逆元(逆元素)

1.费马小定理

如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)

引用一个大神的笔记:https://zhuanlan.zhihu.com/p/372089693?utm_source=wechat_session&utm_medium=social&utm_oi=775109650671476736

通过逆元的定义公式( [公式] )和费马定理的推论公式( [公式] )

得到(条件:a,p互素)

 [公式]

例如7d = 1 mod 40 

 这里出现了一个模幂运算,如何求模幂

2.欧拉定理求逆元 (相当于费马小定理的扩展)

3.扩展欧几里德

4.递推打表

一般使用费马小定理和和费马小定理的推广求逆元

3.取模运算代码实现

本文来自博客园,作者:Jaoany,转载请注明原文链接:https://www.cnblogs.com/fanglijiao/p/15072049.html

原文地址:https://www.cnblogs.com/fanglijiao/p/15072049.html