编程题：数论中的模幂运算
设$$a, m, n\in Z^+$$，且$$a\times n\leq 2^{30}$$, 试计算：$$a^m (\rm{mod}\space \it{n})$$，即求$$a$$的$$m$$次方再对$$n$$求余，并给出$$a$$参与的乘法次数。
### 输入格式:
在一行内输入三个正整数$$a, m$$和$$n$$，用空格隔开，要求$$a\times n\leq 2^{30}$$
### 输出格式:
$$a^m (\rm{mod}\space \it{n})$$的结果，大小不超过$$2^{31}-1$$
### 输入样例1:
in
2 4 5
### 输出样例1:
out
1 1
### 输入样例2:
in
22 418 53
### 输出样例2:
out
7 1
### 提示：
对于幂运算，有：
**规则1**：设$$(m)_{10}=(b_kb_{k-1}b_{k-2}\cdots b_2b_1b_0)_2$$，其中下标代表进制，则有
$$
\begin{array}{ll}
a^m&=a^{b_kb_{k-1}b_{k-2}\cdots b_2b_1b_0}\\
&=a^{b_k\times 2^k+b_{k-1}\times 2^{k-1}+\cdots +b_0\times 2^0}\\
&=a^{b_k\times 2^k}\times a^{b_{k-1}\times 2^{k-1}}\times \cdots \times 2^{b_0\times 2^0}
\end{array}
$$
如
$$
\begin{array}{ll}
5^{(5)_{10}}=5^{(101)_{2}}&=5^{1\times 4}\times 5^{0\times 2}\times
5^{1\times 1}\\
&=((1^2\times 5)^2)^2\times 5
\end{array}
$$
但当$$a$$或$$m$$值很大时，$$a^m$$会很大，甚至超过计算机可以表示的范围（即发生溢出）。此时，在做模幂运算时，不能先求幂再求模。考虑到模运算有：
**规则2**：如果$$a=b\times c$$，则
$$
\begin{array}{ll}
a \space(\rm{mod}\space \it{n})&=(b\times c)\space(\rm{mod}\space \it{n})\\
&=((b\space(\rm{mod}\space \it{n}))\times c)\space(\rm{mod}\space \it{n})\\
&=(b\space(\rm{mod}\space \it{n})\times c\space(\rm{mod}\space \it{n}))\space(\rm{mod}\space \it{n})
\end{array}$$
如
$$
\begin{array}{ll}
5^{(5)_{10}}\space(\rm{mod}\space 8)
&=5^{(101)_{2}}\space(\rm{mod}\space 8)\\
&=(5^{1\times 4}\times 5^{0\times 2}\times 5^{1\times 1})\space(\rm{mod}\space 8)\\
&=((((1^2\space(\rm{mod}\space 8)\times 5)\space(\rm{mod}\space 8))^2\space(\rm{mod}\space 8))^2\space(\rm{mod}\space 8)\times 5)\space(\rm{mod}\space 8)
\end{array}
$$
当$m>n$且$n$是素数时，还可以参考**费马小定理**进行进一步化简：
**规则3**：设$$a,n\in Z^+$$，若$$n$$是素数，且$$\rm{GCD}(\it{a,n})=\rm{1}$$，即$$a$$和$$n$$互质，则有：$$a^{n-1}\space(\rm{mod}\space \it{n})=\rm{1}$$
**举例说明**
$$
\begin{array}{ll}
15^{40}\space(\rm{mod}\space 31)&=((15^{30}\space(\rm{mod}\space 31))\times (15^{10}\space(\rm{mod}\space 31))) \space(\rm{mod}\space 31)\\
&=(1\times (15^{10}\space(\rm{mod}\space 31))) \space(\rm{mod}\space 31)\\
&=15^{10}\space(\rm{mod}\space 31)
\end{array}
$$
同理，有：
$$
\begin{array}{ll}
5^{200}\space(\rm{mod}\space 31)&=
5^{30\times 6+20}\space(\rm{mod}\space 31)\\
&=5^{20}\space(\rm{mod}\space 31)
\end{array}
$$
因此，计算模幂$$a^m \space(\rm{mod}\space \it{n})$$时，请参考如下算法：
$$\bold{\textcolor{blue}{算法}}\textcolor{red}{\rm{ExpMod}}$$
输入：$$a, m, n$$
输出：$$a^m \space(\rm{mod}\space \it{n})$$
1$$\quad$$ **if** $$n$$是素数 **and** $$a$$与$$n$$互质 **and** $$m\geq n$$ **then**
2$$\qquad$$m%=n-1
3$$\quad$$$$c\gets1$$
2$$\quad$$将$$m$$转换为二进制串$$b_{\textcolor{red}{k}}b_{k-1}\cdots b_2b_1b_{\textcolor{red}{0}}$$
3$$\quad$$**for** $$j\gets \textcolor{red}{k}$$ **downto** $$\textcolor{red}{0}$$ **do**
4$$\qquad$$$$c\gets c^2\space (\rm{mod}\space \it{n})$$
5$$\qquad$$**if** $$b_j$$ **then**
6$$\qquad\quad$$$$c\gets ac\space (\rm{mod}\space \it{n})$$
7$$\qquad$$**end_if**
8$$\quad$$**end_for**
9$$\quad$$**return** $$c$$
**注意**：正整数的模(**mod**)运算即求余(**%**)操作。
答案：若无答案欢迎评论
### 输入格式:
在一行内输入三个正整数$$a, m$$和$$n$$，用空格隔开，要求$$a\times n\leq 2^{30}$$
### 输出格式:
$$a^m (\rm{mod}\space \it{n})$$的结果，大小不超过$$2^{31}-1$$
### 输入样例1:
in
2 4 5
### 输出样例1:
out
1 1
### 输入样例2:
in
22 418 53
### 输出样例2:
out
7 1
### 提示：
对于幂运算，有：
**规则1**：设$$(m)_{10}=(b_kb_{k-1}b_{k-2}\cdots b_2b_1b_0)_2$$，其中下标代表进制，则有
$$
\begin{array}{ll}
a^m&=a^{b_kb_{k-1}b_{k-2}\cdots b_2b_1b_0}\\
&=a^{b_k\times 2^k+b_{k-1}\times 2^{k-1}+\cdots +b_0\times 2^0}\\
&=a^{b_k\times 2^k}\times a^{b_{k-1}\times 2^{k-1}}\times \cdots \times 2^{b_0\times 2^0}
\end{array}
$$
如
$$
\begin{array}{ll}
5^{(5)_{10}}=5^{(101)_{2}}&=5^{1\times 4}\times 5^{0\times 2}\times
5^{1\times 1}\\
&=((1^2\times 5)^2)^2\times 5
\end{array}
$$
但当$$a$$或$$m$$值很大时，$$a^m$$会很大，甚至超过计算机可以表示的范围（即发生溢出）。此时，在做模幂运算时，不能先求幂再求模。考虑到模运算有：
**规则2**：如果$$a=b\times c$$，则
$$
\begin{array}{ll}
a \space(\rm{mod}\space \it{n})&=(b\times c)\space(\rm{mod}\space \it{n})\\
&=((b\space(\rm{mod}\space \it{n}))\times c)\space(\rm{mod}\space \it{n})\\
&=(b\space(\rm{mod}\space \it{n})\times c\space(\rm{mod}\space \it{n}))\space(\rm{mod}\space \it{n})
\end{array}$$
如
$$
\begin{array}{ll}
5^{(5)_{10}}\space(\rm{mod}\space 8)
&=5^{(101)_{2}}\space(\rm{mod}\space 8)\\
&=(5^{1\times 4}\times 5^{0\times 2}\times 5^{1\times 1})\space(\rm{mod}\space 8)\\
&=((((1^2\space(\rm{mod}\space 8)\times 5)\space(\rm{mod}\space 8))^2\space(\rm{mod}\space 8))^2\space(\rm{mod}\space 8)\times 5)\space(\rm{mod}\space 8)
\end{array}
$$
当$m>n$且$n$是素数时，还可以参考**费马小定理**进行进一步化简：
**规则3**：设$$a,n\in Z^+$$，若$$n$$是素数，且$$\rm{GCD}(\it{a,n})=\rm{1}$$，即$$a$$和$$n$$互质，则有：$$a^{n-1}\space(\rm{mod}\space \it{n})=\rm{1}$$
**举例说明**
$$
\begin{array}{ll}
15^{40}\space(\rm{mod}\space 31)&=((15^{30}\space(\rm{mod}\space 31))\times (15^{10}\space(\rm{mod}\space 31))) \space(\rm{mod}\space 31)\\
&=(1\times (15^{10}\space(\rm{mod}\space 31))) \space(\rm{mod}\space 31)\\
&=15^{10}\space(\rm{mod}\space 31)
\end{array}
$$
同理，有：
$$
\begin{array}{ll}
5^{200}\space(\rm{mod}\space 31)&=
5^{30\times 6+20}\space(\rm{mod}\space 31)\\
&=5^{20}\space(\rm{mod}\space 31)
\end{array}
$$
因此，计算模幂$$a^m \space(\rm{mod}\space \it{n})$$时，请参考如下算法：
$$\bold{\textcolor{blue}{算法}}\textcolor{red}{\rm{ExpMod}}$$
输入：$$a, m, n$$
输出：$$a^m \space(\rm{mod}\space \it{n})$$
1$$\quad$$ **if** $$n$$是素数 **and** $$a$$与$$n$$互质 **and** $$m\geq n$$ **then**
2$$\qquad$$m%=n-1
3$$\quad$$$$c\gets1$$
2$$\quad$$将$$m$$转换为二进制串$$b_{\textcolor{red}{k}}b_{k-1}\cdots b_2b_1b_{\textcolor{red}{0}}$$
3$$\quad$$**for** $$j\gets \textcolor{red}{k}$$ **downto** $$\textcolor{red}{0}$$ **do**
4$$\qquad$$$$c\gets c^2\space (\rm{mod}\space \it{n})$$
5$$\qquad$$**if** $$b_j$$ **then**
6$$\qquad\quad$$$$c\gets ac\space (\rm{mod}\space \it{n})$$
7$$\qquad$$**end_if**
8$$\quad$$**end_for**
9$$\quad$$**return** $$c$$
**注意**：正整数的模(**mod**)运算即求余(**%**)操作。
答案：若无答案欢迎评论