题目描述

给定两个正整数 \(m\) 和 \(n\)，要求计算 \(m^n\) 的值。最直接的做法是将 \(m\) 连续乘 \(n\) 次（即进行 \(n-1\) 次乘法），然而这是一种效率较低的方法。本题希望你设计并实现一个高效的计算方法，使用递归和分治的思想来减少乘法次数。

在程序中，需要输出：

1. \(m^n\) 的计算结果。
2. 为得到该结果所使用的 最少乘法次数。

请注意，题目强调以减少乘法次数为目标；如果你的程序始终输出 \(n-1\)（或者接近这个值）的乘法次数，就说明没有利用好分治方法。

输入格式

输入只有一行，包含两个正整数 \(m\) 和 \(n\)（\(1 \leq m \leq 10\ , n \leq 15\)) 以内，视题目要求可适当调整上限）。

输出格式

输出两行：

1. 第一行：\(m^n\) 的计算结果。
2. 第二行：最少使用的乘法次数（不包括任何加法、赋值、函数调用等，仅指乘法操作本身）。

样例 1

输入：

2 10

输出：

1024
4

解释：

• \(2^{10} = 1024\)
• 若用连乘法：需 \(10-1=9\) 次乘法。
  实际：
  1. 2 × 2 = 4
  2. 4 × 4 = 16
  3. 16 × 16 = 256
  4. 256 × 4 = 1024 只需要4次即可

样例 2

输入：

2 16

输出：

65536
4

解释：

• 计算 (2^{16}) 的连乘法需要 (16-1=15) 次乘法；
• 使用分治递归的方法，可以按以下步骤计算：
  1. 计算 (2^2 = 2 \times 2) ，使用 1 次乘法。
  2. 计算 (2^4 = (2^2)^2) ，使用 1 次乘法。
  3. 计算 (2^8 = (2^4)^2) ，使用 1 次乘法。
  4. 计算 (2^{16} = (2^8)^2) ，使用 1 次乘法。

总共只需要 4 次乘法，远小于 15 次