大整数幂模分解公式
m a + b m o d q = ( m a × m b ) q = ( ( m a m o d q ) × ( m b m o d q ) ) m o d q \begin{aligned}
m^{a+b} \space mod \space q
&=(m^a \times m^b) \space q\\
&=((m^a \space mod \space q)\times (m^b \space mod \space q)) \space mod \space q\\
\end{aligned}
m a + b m o d q = ( m a × m b ) q = ( ( m a m o d q ) × ( m b m o d q ) ) m o d q
证明:
设
m a + b m o d q = t m^{a+b} \space mod \space q = t m a + b m o d q = t
m a m o d q = t 1 m^{a} \space mod \space q = t_1 m a m o d q = t 1
m b m o d q = t 2 m^{b} \space mod \space q = t_2 m b m o d q = t 2
等价于
m a + b ÷ q = x ⋯ t m^{a+b} \space \div \space q = x \cdots t m a + b ÷ q = x ⋯ t
m a ÷ q = x 1 ⋯ t 1 m^{a} \space \div \space q = x_1 \cdots t_1 m a ÷ q = x 1 ⋯ t 1
m b ÷ q = x 2 ⋯ t 2 m^{b} \space \div \space q = x_2 \cdots t_2 m b ÷ q = x 2 ⋯ t 2
其中x , x 1 , x 2 x,x_1,x_2 x , x 1 , x 2 为整数
则有
x q + t = m a + b xq+t=m^{a+b} x q + t = m a + b
x 1 q + t 1 = m a x_1 q+t_1=m^a x 1 q + t 1 = m a 即t 1 = m a − x 1 q t_1=m^a-x_1 q t 1 = m a − x 1 q
x 2 q + t 2 = m b x_2 q+t_2=m^b x 2 q + t 2 = m b 即t 2 = m b − x 2 q t_2=m^b-x_2 q t 2 = m b − x 2 q
( ( m a m o d q ) × ( m b m o d q ) ) m o d q = ( t 1 × t 2 ) m o d q = ( m a × m b − x 2 q m b − x 1 q m a + x 1 x 2 q 2 ) m o d q = ( m a + b m o d q − ( x 2 m b + x 1 m a ) q m o d q + x 1 x 2 q 2 m o d q ) m o d q = m a + b m o d q
((m^a \space mod \space q)\times (m^b \space mod \space q)) \space mod \space q \\
\begin{aligned}
&=(t_1 \times t_2) \space mod \space q\\
&=(m^a \times m^b-x_2qm^b-x_1qm^a+x_1x_2q^2) \space mod \space q\\
&=
(m^{a+b}mod \space q
-(x_2m^b+x_1m^a)q \space mod \space q
+x_1x_2q^2 \space mod \space q
) \space mod \space q\\
&=m^{a+b} \space mod \space q
\end{aligned}
( ( m a m o d q ) × ( m b m o d q ) ) m o d q = ( t 1 × t 2 ) m o d q = ( m a × m b − x 2 q m b − x 1 q m a + x 1 x 2 q 2 ) m o d q = ( m a + b m o d q − ( x 2 m b + x 1 m a ) q m o d q + x 1 x 2 q 2 m o d q ) m o d q = m a + b m o d q
证明完毕,即
m a + b m o d q = ( ( m a m o d q ) × ( m b m o d q ) ) m o d q m^{a+b} \space mod \space q =((m^a \space mod \space q)\times (m^b \space mod \space q)) \space mod \space q
m a + b m o d q = ( ( m a m o d q ) × ( m b m o d q ) ) m o d q
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int solve (int m, int n, int q) { if (n == 1 ) return m % q; int s = solve(m, n / 2 , q); int r = s * s % q; if (n % 2 ) return (r * (m % q)) % q; return s * s % q; }