专题-D-大数运算.md

专题-大数运算

Index

• 大数取模
  • 取模运算的性质
  • 快速幂取模
• 大数加/减/乘/除

大数取模

取模运算的性质

• 因为 (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
              == ...
    

大数加/减/乘/除

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