$O(V)$ 预处理 $O(1)$ 查询 $\text{gcd}$。
首先考虑将每个数 $n$ 分解成 $a,b,c$,满足 $a\le b\le c$ 且若 $c\gt \sqrt n$ 则 $c$ 一定是质数。
利用线性筛处理上述过程,线性筛会枚举 $n$ 的最小素因子 $p$,假设 $\frac np$ 的分解为 $a',b',c'$,则 $n$ 的分解为 $a'p,b',c'$。
下面进行正确性的证明:
若 $p\le n^{\frac 14}$,由于 $a'\le (\frac np)^{\frac 13}$,于是 $a'p\le \sqrt n$,成立。
若 $p\gt n^{\frac 14}$,由于 $p$ 是 $n$ 的最小素因子,所以 $n$ 的其他因子不超过两个,所以 $a'=1$,即 $a'p$ 是素数,也成立。
接下来考虑计算 $gcd(x,y)$,设 $y=abc$,于是可以先计算 $x,a$ 的公因数,再令 $x$ 除以 $a$,依次处理 $b,c$ 的贡献。
于是只需要考虑 $gcd(x,a)=gcd(x\bmod a,a)$ 如何计算,根据分解规则知 $a$ 要么为素数要么不超过 $\sqrt V$。
若 $a$ 是素数只需要考虑是否整除即可,否则可以 $O(V)$ 预处理出任意两个不超过 $\sqrt V$ 的数的 $\text{gcd}$ 然后 $O(1)$ 查询。