大数运算

优质

小牛编辑

142浏览

2023-12-01

大数取模

取模运算的性质

因为 (a%n) - (b%n) 可能小于 n，所以 +n
因为 (a%n)(b%n) 可能溢出，计算前应该强转为 long long

Code - C++

输入 a 为长度小于 1000 的字符串，b 为小于 100000 的整数

int big_mod(const string& a, int b) {
    long ret = 0;  // 防止 ret * 10 溢出
    for (auto c : a) {
        ret = ((ret * 10) % b + (c - '0') % b) % b;  // ret = ((ret * 10) + (c - '0')) % b
    }
    return (int)ret;
}

/* 示例说明
1234 % 11 == ((((0*10 + 1)*10 + 2)*10 + 3)*10 + 4) % 11
          == ((((0*10 + 1)*10 + 2)*10 + 3)*10 % 11 + 4 % 11) % 11
          == ((((0*10 + 1)*10 + 2)*10 % 11 + 3 % 11)*10 % 11 + 4 % 11) % 11
          == ((((0*10 + 1)*10 % 11 + 2 % 11)*10 % 11 + 3 % 11)*10 % 11 + 4 % 11) % 11
          == ((((0*10 % 11 + 1 % 11)*10 % 11 + 2 % 11)*10 % 11 + 3 % 11)*10 % 11 + 4 % 11) % 11

快速幂取模

计算 a^n % b

基本方法：根据取模的性质 3 —— ab % m == (a%m)(b%m) % m

int big_mod(int a, int n, int b) {
    long long ret = 1;
    while(n--) {
        ret *= a % b;
        ret %= b;
    }
    return (int)ret;

}

时间复杂度 O(N)

快速幂取模

int big_mod(int a, int n, int b) {
    long long ret = 1;
    while(n) {
        if (n & 1)
            ret = (ret*a) % b;
        a = (a*a) % b;
        n >>= 1;
    }
    return (int)ret;
}

代码跟快速幂很像

示例说明

2^10 % 11 == (2^5 % 11)(2^5 % 11) % 11
          == ((2 % 11)(2^4 % 11))((2 % 11)(2^4 % 11)) % 11
          == ...

大数加/减/乘/除

大数的四则运算（加法、减法、乘法、除法） - 落枫飘飘 - 博客园