大数求余解法

大数求余

分循环求余、快速幂求余，其中后者时间复杂度更低，两种方法均基于以下求余运算规则推出：

  (xy) % p = [(x % p)(y % p)] % p

1. 循环求余

   • 根据求余运算性质推出（假设x < p)

     • x^a % = [(x^a-1 % p)(x % p)] % p = [(x^a-1 % p)x] % p

   • 利用此公式，通过循环操作依次求x¹,x²,……，x^a-1,x^a对p的余数保证每轮中间值都在int32的取值范围中

   • 时间复杂度O(N),即循环的线性复杂度

     # 求 (x^a) % p —— 循环求余法
     def remainder(x, a, p):
         rem = 1
         for _ in range(a):
             rem = (rem * x) % p
         return rem

2. 快速幂求余

   • 根据求余运算可推出：

     • x^a % p = (x²)^a/2 % p = (x² % p)^a/2 % p

   • 当a为奇数时a/2不是证书，因此分为两种不同的情况(“//“代表向下取整的除法，当a为偶数或奇数）

     1. x^a % p = (x² % p)^a/2 % p
     2. x^a % p = [(x % p)(x^a-1 % p)] % p = [x(x² % p)^{a//2] % p}

   • 利用以上公式，可通过循环操作每次把指数a问题降低至a//2问题，只需循环log₂（N）次，因此可将时间复杂度降低至对数级别

     # 求 (x^a) % p —— 快速幂求余
     def remainder(x, a, p):
         rem = 1
         while a > 0:
             if a % 2: rem = (rem * x) % p
             x = x ** 2 % p
             a //= 2
         return rem