在acm被称为快速幂(平方求幂) 在ctf中也被称为 $montecarlo$ 先说幂运算的朴素做法，在数学中，重复连乘的运算叫做乘方，乘方的结果称为 幂 ${\displaystyle n}$ 个相同的数 ${\displaystyle b}$ 连续相乘 [公式] // c++ version #include <iostream> int b, n, sum; // 仅作演示, 实际应该使用python或高精度防止爆int int main() { std::cin >> b >> n; if (n == 0) { //对0次幂特判 std::cout << 1; return 0; } sum = b, n = n - 1; while (n --) { sum *= b; } for (int sum) std::cout << sum; return 0; } 让我们先来思考一个问题：7的10次方，怎样算比较快？ 方法1：上述提到的朴素算法, 来计算 $7 *7=49$，$49* 7=343$ / 这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。 / 方法2：先算7的5次方，即$7 *7* 7 *7* 7$，再算它的平方，共进行了5次乘法。 / 方法3：先算7 *7得49，则7的5次方为$49* 49 \* 7$，再算它的平方，共进行了4次乘法。

构造+贪心(R1000) / 剩余24h A. Find Amir / # 有n个地点，每来往i，j两个地点就花费（i+j）mod（n+1），问遍历所有地点的最低花费 # 当i+j==n+1每两地花费最小，如1, n; 2，n-1 # 只需以1->n->2->n-1->3...这样的顺序花费就最小 n = int(input()) res = 0 # res = (n-1)/2 if n & 1: # n is odd res = (n - 1) >> 1 else: res = (n >> 1) - 1 print(res) by: 易如鱼 & aYi_7 & 张少锋 / 分析：由于花费是要（i+j）mod（n+1），则尽可能使每段路程的i+j都接近n+1，通过样例中n=10的情况，不难发现解法。从1到n，花费为0(11%11 = 0)；从n走到2，花费为1(12%11=1)；从2到n-1，花费为0；从n-1到3，花费为1;从3到n-2…这样循环往复，每次向右走花费为零，向左走花费为1。据此不难写出通项公式：cost =（n-1）mod 2。