模运算性质、快速幂（取模）

2024-07-16 05:53| 来源: 网络整理| 查看: 265

模运算的一些性质同余公式

形如a≡b (mod d)的式子被称为同余公式，因为此式中a与b模d后的值相等，故被称为同余公式。相关性质将基于它展开。

它等价于(a-b)|d、a-(a/d)*d=b、a=b+nd (n∈Z)。

运算性质a≡a(mod d)对称性 a≡b (mod d)→b≡a (mod d)传递性 (a≡b (mod d),b≡c (mod d))→a≡c (mod d)如果a≡x (mod d),b≡m (mod d),则 a+b≡x+m (mod d) a-b≡x-m (mod d) a*b≡x*m (mod d ) a/b≡x/m (mod d)a≡b (mod d)则a-b|da≡b (mod d)则an≡bn (mod d)如果ac≡bc (mod m)，且c和m互质，则a≡b (mod m）运算规则

(a + b) mod p = (a mod p + b mod p) mod p (a – b) mod p = (a mod p – b mod p) mod p (a * b) mod p = (a mod p * b mod p) mod p ab mod p = ((a mod p)b) mod p 结合率： ((a + b) mod p + c) mod p = (a + (b + c) mod p) mod p ((a * b) mod p * c) mod p = (a * (b * c) mod p) mod p 交换率： (a + b) mod p = (b+a) mod p (a * b) mod p = (b * a) mod p 分配率： ((a + b) mod p * c) mod p = ((a * c) mod p + (b * c) mod p) mod p 重要定理：若a≡b (mod p)，则对于任意的c，都有(a + c) ≡ (b + c) (mod p) 若a≡b (mod p)，则对于任意的c，都有(a * c) ≡ (b * c) (mod p) 若a≡b (mod p)，则对于任意的c，都有ac≡ bc (mod p)

快速幂（取模）简介

快速幂是运用分治思想降低朴素算法复杂度的算法，是OI中大数据常用的优化小trick。

说明

假设我们现在正在解决求a^b的问题，其中b非常大，而且通常会遇到朴素算法运算中，中间得数就已经会爆int甚至爆long long的情况。

我们知道a^b=(a^(b/2))^2，因此我们可以将求a^b问题转化为求a^(b/2)问题，如此递归下去，总会遇到b/2=0的时候，此时递归就到头了。这样做的时间复杂度是O(logn)的（而朴素是O(n)的）。

我们还可以运用取模运算的性质(a * b) mod p = (a mod p * b mod p) mod p来对每一步的值取模缩小值的范围。此算法便是边幂边取模的算法。

如果b是一个单数怎么办？也不要紧：a^b=(a^(b/2))^2*a即可解决。

代码

下面是递归式快速幂。

int fpow(int x, int p) { // 求x^p if(p == 0) return 1; int t = fpow(x, p / 2); if(p % 2 == 0) { return t * t; } else { return t * t * x; } } int fpow_m(int x, int p, int m) { // 求(x^p)%m if(p == 0) return 1; int t = fpow_m(x, p / 2, m) % m; if(p % 2 == 0) { return (t * t) % m; } else { return ((t * t) % m * (x % m)) % m; } }

下面是非递归式快速幂。

inline LL fpow(LL x, LL k) { LL t = 1; while(k) { if(k & 1) t = (t * x) % MO; x = (x * x) % MO; k >>= 1; } return t; } 应用

应用不用说了，常用于数据大的NOIP提高组复赛T1之类的题目。

参考资料

模运算与同余公式的性质 – 根号下的麻辣烫 – CSDN博客

例题：2011 北大OpenJudge百练4010描述已知长度最大为200位的正整数n，请求出2011^n的后四位。输入第一行为一个正整数k，代表有k组数据，k

【本文地址】

模运算性质、快速幂（取模）

模运算性质、快速幂（取模）

今日新闻

推荐新闻