x^nmod m怎么求

要计算$x^n \mod m$，可以使用快速幂算法。

快速幂算法基于以下原理：对于任意正整数 $x$ 和非负整数 $n$，都可以表示为 $x^n$ 的形式，其中 $n$ 可以表示为二进制形式，例如 $n = b_k 2^k + b_{k-1} 2^{k-1} + ... + b_1 2^1 + b_0 2^0$，其中 $b_i$ 表示二进制下的第 $i$ 位是 $0$ 还是 $1$。因此，我们可以将 $x^n$ 表示为 $x^{2^k} \cdot x^{2^{k-1}} \cdots x^{2^1} \cdot x^{2^0}$ 的形式，其中 $x^{2^i}$ 可以通过连续平方 $i$ 次 $x$ 得到。

使用快速幂算法，我们可以在 $O(\log n)$ 的时间复杂度内计算出 $x^n \mod m$。具体步骤如下：

1. 初始化 $result = 1$ 和 $base = x$。
2. 将 $n$ 表示为二进制形式，从高位到低位依次处理每一位：
- 如果当前位是 $1$，则将 $result$ 乘上 $base$ 的当前幂次。
- 将 $base$ 的幂次乘以 $2$。
3. 返回 $result \mod m$。

下面是一个 Python 代码实现：

def power_mod(x, n, m):
    base = x
    result = 1
    while n > 0:
        if n % 2 == 1:
            result = (result * base) % m
        base = (base * base) % m
        n //= 2
    return result

使用该函数计算 $x^n \mod m$，只需要调用 `power_mod(x, n, m)` 即可。