这其实是一道洛谷模板题，题目是5435
对预处理的讲解可以看看这个博客（代码看自己的，见下）
void getprime()
{
for(int i=0;i<=2;i++) fac[1][i]=1;
for(int i=2;i<=N-10;i++)
{
if(!v[i])
{
v[i]=i;
prime[++tot]=i;
fac[i][0]=fac[i][1]=1;
fac[i][2]=i;
}
for(int j=1;j<=tot;j++)
{
if(prime[j]>v[i]||(ll)i*prime[j]>N-10) break;
int tmp=i*prime[j];
v[tmp]=prime[j];
fac[tmp][0]=fac[i][0]*prime[j];
fac[tmp][1]=fac[i][1];
fac[tmp][2]=fac[i][2];
if(fac[tmp][0]>fac[tmp][1]) {
fac[tmp][0]^=fac[tmp][1]^=fac[tmp][0]^=fac[tmp][1];
}
if(fac[tmp][1]>fac[tmp][2]) {
fac[tmp][1]^=fac[tmp][2]^=fac[tmp][1]^=fac[tmp][2];//这个操作就是升序排序
}
}
}
}
void init()
{
for(int i=0;i<=M-10;i++)
pre[i][0]=pre[0][i]=i;
for(int i=1;i<=M-10;i++)
for(int j=1;j<=i;j++)
pre[i][j]=pre[j][i]=pre[j][i%j];
}
那么这篇博客对查询的讲解不太细致，其实就是用到一个定理
\(gcd(a \times b \times c,y)=gcd(a,y) \times gcd(b,\frac{y}{d_{1}}) \times gcd(c,\frac{y}{d_{1} d_{2}})\)，其中\(d_{1}=gcd(a,y)\)，\(d_{2}=gcd(b,\frac{y}{d_{1}})\)
这个定理的证明暂时不详，有机会可以了解
但是查询时一定要注意，某一次的x可能是质数，此时想的分解为1,1,x，那么这个时候就别用预处理的数组了，可能会超出范围，这个时候特判即可，代码见下
int gcd(int a,int b)
{
int d1,d2,d3;
d1=pre[fac[a][0]][b%fac[a][0]];
b/=d1;
d2=pre[fac[a][1]][b%fac[a][1]];
b/=d2;
if(v[fac[a][2]]==fac[a][2])
{
if(b%fac[a][2]==0) d3=fac[a][2];
else d3=1;
}
else d3=pre[fac[a][2]][b%fac[a][2]];
return (ll)((ll)d1*d2)%p*d3%p;
}