一个小知识点

光速幂

快速幂

先给个快速幂代码：

int qpow(int x, int y)
{
    int res = 1;
    while (y)
    {
        if (y & 1)
            res = res * x % P;
        x = x * x % P;
        y >>= 1;
    }
    return res;
}

快速幂可以在 $O(\log y)$ 的时间求出 $x^y$ ，且实现简单，是很常用的算法

但是，在一些黑心出题人看来，还是不够快

限制

为了有更快的方法，出题人必须给你一些额外的条件：

1. 模数不变，即多次求 $x^y \pmod p$ 时， $p$ 保证不变，这个一般题目都能满足（其实可以变，但每变一次就要一个 $\sqrt{p}$ ）
2. 底数不变，即 $x^y \pmod p$ 时， $x$ 不变，这是光速幂最大的限制

有了如上限制，来看如何把 $O(\log y)$ 的快速幂改为预处理 $O(\sqrt{p})$ ，询问 $O(1)$ 的光速幂，其实很简单

思想

根据欧拉定理 $x^y \equiv x^{y \mod \varphi(p)} \pmod p$ ，于是可以预处理到 $\varphi(p)$ （为了方便一般处理到 $\sqrt{p}$ ）

具体地，预处理出 $x^1, x^2, …, x^{\sqrt{p}}$ 和 $x^{2\sqrt{p}}, x^{3\sqrt{x}}, …$

然后，对于询问 $x^y$ ，令 $p’ = \sqrt{p}$ ，可以回答 $x^{y \mod p’} * x^{(y / p’) * p’}$

代码

#include <bits/stdc++.h>
#define LL long long
const int P = 1e9 + 7;
const int BL = (1 << 16) + 5, B = sqrt(P);
int qp[BL][2];
int ph;
int phi(int x)
{
    int res = x;
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
            res = res / i * (i - 1);
        while (x % i == 0)
            x /= i;
    }
    if (x > 1)
        res = res / x * (x - 1);
    return res;
}
void init(int x)
{
    ph = phi(P);
    qp[0][0] = qp[0][1] = 1;
    for (int i = 1; i <= B; ++i)
        qp[i][0] = qp[i - 1][0] * x % P;
    for (int i = 1; i <= B; ++i)
        qp[i][1] = qp[i - 1][1] * qp[B][0] % P;
}
int qqpow(int y)
{
    y %= ph;
    return qp[y % B][0] * qp[y / B][1] % P;
}