c++ - 为什么次幂取余可以写成先乘再取余？

问题描述

a的b次方对c取余可以写成下面的形式

int ans = 1;while (b−−){ ans = ( ans∗a)%c ;}

数学不好，求大神解释一下

问题解答

因为mod有可乘性

设 a=mq+r, b=nq+s. 则

(a*b) mod q = (mnq^2+msq+nrq+rs) mod q = rs mod q = ((a mod q) * (b mod q)) mod q

手机码字有些混乱