幂指模运算特别方式

发表于 更新于 分类于

概述

  • 给定一个数\(a\)，求它对\(m\)取模的结果，该如何计算？
  • 给定一个数\(a^b\)，求它对\(m\)取模的结果，该如何计算？
  • 给定一个数\(a^{b}\)，其中\(b\)以数组的形式给出\(b=[b_1,b_2,b_3,...,b_n]\)，此时乘积会很大，数值类型将会溢出，如何计算其对\(m\)取模的值？

方法

数组拆分

幂的计算可以写成递归的形式：
\(a^{[b_1,b_2,...,b_n]}=a^{b_n}*{(a^{[b_1,b_2,...,b_{n-1}]})}^{10}\)

取模转换

俩数相乘取模的结果分别为俩数取模结果的乘积在取模。
\((A * B) \% k = (A \% k)(B \% k) \% k\)
假设：

\(A = a_1k+a_2;B = b_1k+b_2\)

\((A*B) \% k = (a_1k+a_2)(b_1k+b_2) \% k\)

\(=(a_1b_1k^2+(a_1b_2+b_1a_2)k+a_2b_2) \% k\)

$=(a_2*b_2) %k $

再有：

\(A \% k = a_2; B \% k = b_2\)

所以：

\(=(a_2*b_2) \% k = (a_2 \% k)(b_2 \% k) \% k\)

初式得证。