模(%)运算 对 四则运算的封闭性(除法!)

2019-04-13 12:27发布

站内文章 / 模拟电子
11065 0 1342
转自:http://hi.baidu.com/xuhanqiu/item/4ccf1bea93fd4ec6bbf37d12 首先想说的是, a%b. 一般都是a>0,b>0 或 a<0, b>0.   其它情况就不要考虑了。 下面说明了为这么只需要考虑这两种情形。       其次，本文总结了模运算对加法、减法、乘法的封闭性。讨论是除法与模运算之间的关系，从而得到一个实用的公式。 ========================正文(精华在文末...)========================     在数学中,我们做取模运算(a%b)都是假设a,b>0的.但在编程处理时,我们经常会碰到a<0,b<0的情况, 而且计算机自己处理取模运算时,与我们数学求出来的结果还不一样 ( 我们想要的结果就是按数学方法计算出来的), 所以要搞清楚计算机求出来的结果与我们想要的结果之间的联系!! 1.先只考虑a<0的情况   (b>0)
a=-106 b=105 数学上: a % b = 104 计算机: a % b = -1
a=-312 b=105 数学上: a % b = 3    计算机: a % b = -102 在计算机中(使用VC++)做取模运算时:
#include int main()
{
int x;
int y = 105; for (x=110; x>=-110; x--)
   printf("%d %% %d = %d ", x, y, x%y); return 0;
}
   
经过大量测试发现:
若我们不能保证a一定大于0时,结果为负时,我们加上一个b就与我们数学中求 得的结果是一样的. 参加上面介绍的第二个例子 a = -312时 2.不需要考虑b<0, 因为计算机是把它当成-b来处理,所以与b>0一样
#include int main()
{
int x;
int y = -5;
for (x=10; x>=-10; x--)
   printf("%d %% %d = %d ", x, y, x%y); printf("============================= ");
y = 5;
for (x=10; x>=-10; x--)
   printf("%d %% %d = %d ", x, y, x%y);
return 0;
} ===========================
模运算有很多性质
(a+b)%n = (a%n + b%n) % n;
(a*b)%n = ((a%n)*(b%n)) % n;
(a-b)%n = (a+(-b))%n = ( (a%n) + ((-b)%n) ) % n 若结果为负,加上n即可
(a/b)%n 没有这个性质了，呵呵~~           取模运算对加法、减法、乘法都封闭，所以我们很容易计算(a+b)mod m，(a-b)mod m，(a*b)mod m。但是，要计算(a/b) mod m就不是那么容易了。 下面首先介绍一个通用公式:                              (a / b) % m = ( a % (m*b)) / b    --- 推导见文末 除了上面的公式，还有一些特殊的情况, eg: m和b互素的时候。 1. 当gcd(b,m) = 1, 有性质: (a/b)%m = (a*b^-1)%m, 其中b^-1是b模m的逆元. 求出b相对于m的逆元b^(-1)，即b*(b^(-1)) = 1 (mod m)。有b*b^(-1) - km = 1，其中k是一整数. 用Extended Euclid算法可以求出`b^(-1)。然后计算a*b^(-1) mod m = ( (a%m) * (b^(-1)%m ) % m; 其值与(a/b) mod m相同 推导：a/b = x (mod m) --两边同乘一个数--> a = bx (mod m) ---x=b^-1a-> a = (b^-1) ba (mod m) 再利用b^-1*b = 1(mod m) . 所以可以得出 x = b^-1*a是成立的。       所以 (a/b) mod m 的解与 (a*b^-1)%m的解是一样的。 而后着可以利用模对乘法的线性性 2. 当gcd(b,m)!=1时怎么办? 此时方程`b*b^(-1) - km = 1`无整数解，求逆元的方法失效了。 ----目前自己只会上面的那个通用公式来求。上面的公式推导如下(目标是求 (a/b) % m): 由于b | a, 所以a = k, 然后将k对m做带余法法，得: a = tmb+rb(其中r                                  (a / b) % m = (tm+r) % m = r, 现在目标就是r。 我们可以等价的求出r。由于r http://acm.fzu.edu.cn/contest/cproblem.php?cid=1073&pid=1 Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,B,C<2^63). A^B mod C: ---------呵呵，刚刚解决这个题，两次二分(多出来的一次二分是解决(A*B)%C的溢出问题)。这也说明通用公式还是有很多用武之地的，只要m*b<2^63 -- （当然，更大时怎么办，高精度么？待整理）

热门文章