最少乘法次数 - 快速幂算法优化C++实现

"一种解法是使用快速幂算法，即将指数n表示为二进制形式，然后根据每个二进制位上的值进行相应的乘法操作。\n\n具体步骤如下：\n1. 将指数n转换为二进制形式，得到一个由0和1组成的数组binary，binary的长度即为所需的最少乘法次数。\n2. 初始化一个变量result为2，用于保存乘法的结果。\n3. 从binary的最低位开始遍历，如果该位上的值为1，则将result与自身相乘，得到新的result。接着将result的平方赋值给result。\n4. 遍历结束后，result的值即为所需的最少乘法次数。\n\n具体实现如下：\n\ncpp\n#include <iostream>\n#include <vector>\nusing namespace std;\n\nint main() {\n int m;\n cin >> m;\n while (m--) {\n int n;\n cin >> n;\n \n // 将指数n转换为二进制形式\n vector<int> binary;\n while (n > 0) {\n binary.push_back(n % 2);\n n /= 2;\n }\n \n // 初始化result为2\n int result = 2;\n \n // 从binary的最低位开始遍历\n for (int i = binary.size() - 2; i >= 0; i--) {\n // 如果该位上的值为1，则将result与自身相乘\n if (binary[i] == 1) {\n result *= result;\n result *= 2;\n }\n // 将result的平方赋值给result\n result *= result;\n }\n \n cout << binary.size() - 1 << endl;\n }\n return 0;\n}\n\n\n时间复杂度分析：\n假设指数n的二进制表示有k位，则最少乘法次数为k-1次。因此，对于每组测试数据，时间复杂度为O(k)。而k的最大值为log2(n)，因此总的时间复杂度为O(m * log2(n))。\n