-
结论：设 \(l=2^k,r=2^{k+1}-1\)，则 \(g(r)-g(l)\leq 1\)。因为 \(g(l) \geq 2\)，而 \(r<2l\)，因此区间 \([l,r]\) 内最多有一个 \(y^k\)。
-
因此先枚举 \(i=\log_2 x\)，可以得到底数不变的一个范围 \([L,R]\)，记 \(logL=\log_i L,p=i^{logL+1}\)，判断 \(p\) 是否在区间内即可。
-
复杂度 \(O(Q \log^2 V)\)，预处理快速幂可以做到 \(O(Q \log V)\)。