题意
这可能也是一道模板题。
给出正整数 \(x\) 和 \(n\) 个正整数 \(a_i\),求 \(x^{a_i} \bmod p\)。
对于 \(100\%\) 的数据,\(1\leq n\leq 5\times 10^6,1\leq x,a_i<p,p=99824435\color{red}2\)。
题解
\(O(\sqrt n)\ - \ O(\ 1\ )\) 光速幂板子。适用于固定底数、较多询问的快速幂查询。支持非质数模数。
具体是像 \(\text{BSGS}\) 算法那样,预处理出 \(x^1,x^2,...x^{\sqrt n}\),随后预处理出 \(x^{\sqrt n},x^{2\sqrt n},...x^n\)。
然后就赢麻了。对于每个查询的指数 \(y\) ,答案即为 \(x^{y ÷ \sqrt n}\ ·x^{y\ mod \sqrt n}\)。这俩上面都是预处理好的。
代码
ll x,n;
const ll mod=998244352;
ll s[32000],b[32000];
void solve(){
x=R,n=R;
ll block=sqrt(mod);
ll bas=1;
b[0]=s[0]=bas;
for(ll i=1;i<=block;i++){
bas=bas*x%mod;
s[i]=bas;
}
x=bas,bas=1;
for(ll i=1;i<=block;i++){
bas=bas*x%mod;
b[i]=bas;
}
while(n--){
ll a=R;
wk(b[a/block]*s[a%block]%mod);
}
return ;
}
标签:LOJ,ll,sqrt,leq,162,预处理,模板,mod
From: https://www.cnblogs.com/rnfmabj/p/loj162.html