ABC238G Cubic?

题意:给定 n 个数的序列,每次询问一段区间的乘积是不是立方数。n,q2×105Ai106,3s。

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

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

注意到一个 NO 在单次判断中被判成 YES 的概率大概是 13,于是我们可以考虑判断 1015 次,这样准确的概率已经极高了。这样就可以通过了,但是可能需要卡常。

但其实有更好的办法,就是把多位压成一个数,这样就是三进制不进位加法,假设有 w 位的话,容易发现准确率是 113w 的。这个对应到判断平方就是 xor 操作,同样也是这样。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;
}

Gitalking ...