取模运算

太过爱你忘了你带给我的痛 2022-05-17 06:22 771阅读 0赞

取模运算（“Modulo Operation”）和取余运算（“Complementation ”）两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机术语中。取余则更多是数学概念。模运算在[数论][Link 1]和程序设计中都有着广泛的应用，比如：

从奇[偶数][Link 2]的判别

素数的判别

模[幂运算][Link 3]

[最大公约数][Link 4]的求法

孙子问题

[凯撒密码][Link 5]问题

虽然很多数论教材上对模运算都有一定的介绍，但多数都是以纯理论为主，对于模运算在程序设计中的应用涉及不多。

为什么需要求余数呢？

如果计算结果超出64位整数范围，就可能会输出结果对某个数取模后的结果。这样可以消除在高精度方面，由于语言的差异造成的不公和一些不利因素。例如，java里有支持高精度的类BIGINTEGER，python整数基本没有范围一说，而c系列就要靠自己实现。

另一方面，高精度乘法不同实现的复杂度也不一样，对算法本身的评价更为困难。为了将重点放在对算法本身的评价上，竞赛中经常出现取余运算。

我们不需要掌握太多相关运算规则，够用即可。

1、n % p 得到结果的正负由被除数n决定,与p无关。例如：7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3。

2、大数取模可能比小数取模得出的结果更小，所以要输出最后结果可能是负数，我们可以这样输出：

(A-B+MOD)%MOD,其中AB是取模以后的数。

3、 (a + b) % p = (a % p + b % p) % p

(a - b) % p = (a % p - b % p) % p

(a \* b) % p = (a % p \* b % p) % p

a ^ b % p = ((a % p)^b) % p

贴几个大水问题code好了

快速幂取模

long long quick_mod(long long a, long long n, long long m)
    {
        long long ans = 1;
        while (n)
        {
            if (n & 1)
                ans = (ans * a) % m;
            n >>= 1;
            a = a * a % m;
        }
        return ans;
    }

乘法取模

long long mul_mod(long long a, long long b, long long m) // a * b % m
    {
        long long ret = 0;
        while (b)
        {
            if (b & 1)
                ret = (ret + a) % m;
            b >>= 1;
            a = (a << 1) % m;
        }
        return ret;
    }

哦，最后提醒自己，以后遇见题直接上long long，再int自己扇自己

[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E8%AE%BA
[Link 2]: https://baike.baidu.com/item/%E5%81%B6%E6%95%B0
[Link 3]: https://baike.baidu.com/item/%E5%B9%82%E8%BF%90%E7%AE%97
[Link 4]: https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0
[Link 5]: https://baike.baidu.com/item/%E5%87%AF%E6%92%92%E5%AF%86%E7%A0%81