数的高次幂运算取余，解决大数溢出问题

2023-12-30 05:28:45

解决思路

当一个幂运算很大，而模为整型数时，通常的做法（先求幂再取模），结果很大可能就是数溢出，无法表示这样的大数，导致运算失败。 可以先试着将数分割成几个部分，然后一个部分一部分的求取模数，从而实现目的。

基础数学公式

因此我们可以利用以下的公式可以有效的避免这一问题

公式1证明：

数学公式： (a * b ) mod C = (( a mod C) * b) mod C; (a, b, C 皆是是整数)
设：a=m+k, m 的值为 C 的 n 倍数（n>=0，且为整数）, k < C

则:
(a * b ) mod C= ( ( m + k ) * b ) mod C = ( mb + kb ) mod C = ( Cnb + kb ) mod C

( Cnb + kb ) mod C = kb mod C

因为：

k = a mod C

所以：

(a * b ) mod C = ( ( a mod C ) * b ) mod C

公式2证明：

数学公式
a ? b m o d C = ( a m o d C ) ? ( b m o d C ) m o d C ( a , b , C 皆是是整数 ) a * b\quad mod \quad C = ( a\quad mod \quad C) * ( b\quad mod \quad C) \quad mod\quad C (a, b, C 皆是是整数) a?bmodC=(amodC)?(bmodC)modC(a,b,C皆是是整数)
设： a = m + k 1 , b = n + k 2 , m , n 的值为 C 的 x 倍数（ x > = 0 ，且为整数） , k 1 , k 2 < C a=m+k_1, b=n+k_2, m,n的值为 C 的 x 倍数（x>=0，且为整数）, k_1,k_2 < C a=m+k1?,b=n+k2?,m,n的值为C的x倍数（x>=0，且为整数）,k1?,k2?<C
则：
a ? b = ( m + k 1 ) ? ( n + k 2 ) = m n + m k 2 + k 1 n + k 1 k 2 由于 m 和 n 都是 C 的 x 倍得到： = C x 1 C x 2 + C x 1 k 2 + k 1 C x 2 + k 1 k 2 m o d C = k 1 k 2 m o d C k 1 = a m o d C k 2 = b m o d C 可得： a ? b m o d C = ( a m o d C ) ? ( b m o d C ) m o d C \begin{align*} a*b&=(m+k_1)*(n+k_2)\\ &=mn+mk_2+k_1n+k_1k_2 \\ 由于&m和n都是C的x倍 得到：\\ &=Cx_1Cx_2+Cx_1k_2+k_1Cx_2+k_1k_2 \quad mod \quad C\\ &=k_1k_2\quad mod \quad C\\ k_1&=a \quad mod \quad C\\ k_2&=b \quad mod \quad C\\ 可得：\\ a * b\quad mod \quad C &= ( a\quad mod \quad C) * ( b\quad mod \quad C) \quad mod\quad C \end{align*} a?b由于k1?k2?可得：a?bmodC?=(m+k1?)?(n+k2?)=mn+mk2?+k1?n+k1?k2?m和n都是C的x倍得到：=Cx1?Cx2?+Cx1?k2?+k

文章来源:https://blog.csdn.net/Linux7985/article/details/135296891
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。