光速幂学习笔记 - 算法学习 | 123hh2 = Keep moving forward

# 光速幂

在同一底数 $a$ 和同一模数 $p$ 的情况下，大量询问 $a^x \mod p$ 的时候，可以使用光速幂做到 $O(\sqrt{p})$ 预处理， $O(1)$ 查询

我们选定一个数 $x$ 并处理 $a^0,a^1,a^2 …… a^x$ 和 $a^{0 \times x},a^{1 \times x},a^{2 \times x}……a^{\lceil \frac{p}{x} \rceil \times x}$ ，将答案存入数组便于后续查询

当然，所有的值都要取模

然后我们对于一个询问指数 $k$ ，可以将拆成 $k = k \mod x + \lfloor \frac{k}{x} \rfloor \times x$ ，前者后者都可以在两个数组中 $O(1)$ 查询到

这样我们就实现了 $O \sqrt{p}$ 预处理， $O(1)$ 查询的光速幂

对于特别大的指数，我们可以用欧拉定理 $a^x \equiv a^{x \mod \phi(p)} \mod p$ 将指数降低到可接受的范围

对于 $gcd(a,m) \neq 1$ 的情况可以用 $a^x \equiv a^{x \mod \phi(p) + \phi(p)} \mod p$

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const int maxn=1e5+5;//sqrt(mod)
	const int mod=998244353;
	int get_phi(int n)// 找 phi (mod)
	{
	int ans=n;
	for(int i=2;i*i<=n;i++)
	{
	if(n%i==0) ans=ans/i*(i-1);
	while(n%i==0) n/=i;
	}
	if(n>1) ans=ans/n*(n-1);
	return ans;
	}
	int pre_pow[maxn][2];
	void init(int a)
	{
	int k=sqrt(mod);
	pre_pow[0][0]=pre_pow[0][1]=1;
	for(int i=1;i<=k;i++) pre_pow[i][0]=pre_pow[i-1][0]*a%mod;
	for(int i=1;i<=k;i++) pre_pow[i][1]=pre_pow[i-1][1]*pre_pow[k][0]%mod;
	}
	int fstpow_plus(int a,int b,int k)
	{
	if(b/k>k) return (((pre_pow[b%k][0]pre_pow[b/k-k][1])%mod)pre_pow[k][1])%mod;
	return (pre_pow[b%k][0]*pre_pow[b/k][1])%mod;
	}
	signed main()
	{
	int p=get_phi(mod),k=sqrt(mod);
	int a=read();
	init(a);
	int q=read();
	while(q-->0)
	{
	int b=read();//a^b%mod
	cout<<fstpow_plus(a,b%p,k)<<endl;
	}
	return _123hh2;
	}