ABC238G Cubic?

题意：给定 $n$ 个数的序列，每次询问一段区间的乘积是不是立方数。$n,q\le 2\times {10}^5$，$A_i\le {10}^6$，3s。

注意到我们显然需要对每一个质因数都判断一次，看这段区间有多少个该质因子，观察次幂是否是 3 的倍数即可。但是怎么都不好做，大概都是带根号的平衡做法了。

瓶颈仍然在于我们如何对每个质因子都需要判一边，很浪费时间。于是考虑 Hash，我们令一个质因子是 $[0,2]$ 的任意一个数，然后让和 $mod3$ 的余数看是不是 0。如果不是 0 的话显然答案是 NO。

注意到一个 NO 在单次判断中被判成 YES 的概率大概是 ${\displaystyle \frac{1}{3}}$，于是我们可以考虑判断 $10\sim 15$ 次，这样准确的概率已经极高了。这样就可以通过了，但是可能需要卡常。

但其实有更好的办法，就是把多位压成一个数，这样就是三进制不进位加法，假设有 $w$ 位的话，容易发现准确率是 $1-{\displaystyle \frac{1}{3^w}}$ 的。这个对应到判断平方就是 xor 操作，同样也是这样。

于是直接按照这个写，大概分解一下质因数就好了。时间复杂度 $O(n\sqrt{n}+TQ)$，$T$ 表示判断次数，可以通过。

场上想的降智办法是找到一个数满足 $x^3\equiv 1(\mathrm{mod}p)$，然后对于每一个质因数，任取 $x$ 的几次方作为随机权值，这样的话区间乘积如果不是 1 的话，这个询问是 NO。容易发现其实是一样的。

void work()
{
	static std::mt19937 rnd(std::random_device{}());
	int mul = ((int) 1e9 + 8) / 3;
	for (int i = 0, t; i < cnt; ++ i) {
		while (std::__gcd(t = rnd() % (Mod - 1), Mod - 1) != 1);
		rv[i] = qpow(13, (LL) mul * t % (Mod - 1));
	}
	pre[0] = 1;
	for (int i = 1, x, p, id; i <= n; ++ i)
	{
		x = a[i], pre[i] = pre[i - 1];
		while (x ^ 1) {
			p = mxp[x];
			id = std::lower_bound(prime, prime + cnt, p) - prime;
			while (x % p == 0) pre[i] = (LL) pre[i] * rv[id] % Mod, x /= p;
		}
	}
	for (int i = 1; i <= Q; ++ i)
		res[i] &= (LL) pre[q[i].r] * qpow(pre[q[i].l - 1]) % Mod == 1;
}

int main()
{
	sieve();
	std::cin >> n >> Q;
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	for (int i = 1; i <= Q; ++ i) res[i] = true;
	for (int i = 1; i <= Q; ++ i) scanf("%d %d", &q[i].l, &q[i].r);
	int T = 20;
	while (T --) work();
	for (int i = 1; i <= Q; ++ i) puts(res[i] ? "Yes" : "No");
	return 0;
}