[LOJ#162]模板题-快速幂2

<题目链接>

注意：这可能也是一道模板题。

注意2：$p=998224352$

注意3：对于$100\%$的数据，$n\leq 5 \times 10^6$

这个题很启发思路，如果直接快速幂应该会T飞（不过还是看到卡常大师$997ms$过……）。

所以

法一：直接快速幂

复杂度：$\Theta(N \log p)$

不多说直接快速幂即可。

法二：神奇分块思路

由于询问比较多，我们考虑预处理。

假设我们处理到$k$.

我们在指数上化柿子。

有：

$$\large x^y=x^{y\, \mod\, k }\times x^{\left\lfloor\frac{y}{k}\right\rfloor \times k}$$

然后就可以$\Theta(1)$回答了

预处理是$\Theta(k+\frac{p}{k})$的

于是取$k=p^{\frac{1}{2}}+1$可以达到最优复杂度$\Theta(p^{\frac{1}{2}}+N)$($+1$是为了防止$\sqrt{p}$取整精度跪掉)

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

const int Mod = 998244352, Sqrt = 31596;

long long val[32000], van[32000], vd, qn;

int main() {

    long long q;

    scanf("%lld%lld", &vd, &qn);

    val[0] = 1;

    val[1] = vd % Mod;

    for (int i = 2; i <= Sqrt; i++) val[i] = val[i - 1] * vd % Mod;  // cout<<val[i]<<" ";

    van[0] = 1;

    van[1] = val[Sqrt];

    for (int i = 2; i <= Sqrt; i++) van[i] = van[i - 1] * val[Sqrt] % Mod;

    for (int i = 1; i <= qn; i++) {

        scanf("%lld", &q);

        // cout<<q%Sqrt<<" "<<q/Sqrt<<endl;

        // cout<<val[q%Sqrt]<<" "<<van[q/Sqrt]<<endl;

        printf("%lld ", val[q % Sqrt] * van[q / Sqrt] % Mod);

    }

    puts("");

}

不得不说格式化代码令人兴奋……

巴特西

[LOJ#162]模板题-快速幂2

法一：直接快速幂

法二：神奇分块思路

最新文章

热门文章