模运算的一些性质

同余公式

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

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

运算性质

1. a≡a(mod d)
2. 对称性 a≡b (mod d)→b≡a (mod d)
3. 传递性 (a≡b (mod d),b≡c (mod d))→a≡c (mod d)
4. 如果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)
5. a≡b (mod d)则a-b|d
6. a≡b (mod d)则aⁿ≡bⁿ (mod d)
7. 如果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
a^b  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<=200接下来的k行，

每行都有一个正整数n，n的位数<=200

输出

每一个n的结果为一个整数占一行，若不足4位，去除高位多余的0

样例输入

3
5
28
792

样例输出

1051
81
5521

分析

快速幂是肯定得用的，但是同时也考验了高精度幂运算的知识。

此处我用了一个小trick，打表知取2011的k次幂时，只要整数k后三位相等，他们运算后所得数后四位相等。故省去了写高精度的功夫。

代码

#include <cstdio>
#include <cstring>
#include <cstdlib> 

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; 
    }
}

int n, t;
char s[205];
char tmp[5];

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        memset(s, 0, sizeof s);
        memset(tmp, 0, sizeof tmp);
        scanf("%s", s);
        int len = strlen(s), cnt = 0;
        for(int i = 0; i < 3; i++) {
            if(len - 3 + i < 0) continue;
            tmp[cnt] = s[len - 3 + i];
            cnt++;
        }
        //printf("p: %s\n", tmp);
        printf("%d\n", fpow_m(2011, atoi(tmp), 10000));
    } 
    return 0;
}

参考资料

快速幂+快速幂经典例题 -  - CSDN博客