AtCoder Contest 238 - G 题解

题目内容

Given a sequence \(A\) of \(N\) numbers, answer the following \(Q\) questions.

• In the \(i\)-th question, you are given integers \(L_i\) and \(R_i\) . Is \(A_{L_i} \times A_{L_i+1} \times \dots \times A_{R_i}\)A a cubic number?

Here, a positive integer \(x\) is said to be a cubic number when there is a positive integer \(y\) such that \(x=y^3\) .

给定长为N的序列A，Q 组询问 (l,r)，
判断 (\(\prod \limits_{i=l}^{r}A_i\)) 是否是完全立方数。
\((1 \le N,~Q \le 2 \times 10^5,~1 \le A_i \le 10^6)\).

Hash做法

Code

• 每个质因子生成三个不同的Hash， 满足 \({X_2} = {X_0} \oplus {X_1}\) .
• 逐个质因子更新异或和序列 \(H_j\) , \({H_j} \leftarrow {H_j} \oplus {X_{i\bmod 3}}\) , 使每个质因子三个不同的Hash轮流出现。
• 异或具有交换律和归零律，可得到： \([l, r]\) 区间内每个质因子的个数都是 \(3\) 的倍数 ⇒ \(H_l \oplus H_{l+1} \oplus \dots \oplus H_r = 0\) .（注意，反向不成立）
• 使用异或前缀和 \(H'\) 加快查询速度。

#include<bits/stdc++.h>

#define MAX 1000005

using namespace std;

int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (auto &nx: a)
    { cin >> nx; }
    vector<int> l(q), r(q);
    for (int i = 0; i < q; i++)
    { cin >> l[i] >> r[i]; }

    uint_fast64_t seed = 202202052100238523;
    mt19937_64 engine(seed);
    vector<vector<int>> pf(MAX);
    for (int i = 2; i < MAX; i++)
    {
        if (!pf[i].empty())
        { continue; }
        for (int j = i; j < MAX; j += i)
        {
            int mj = j;
            while (mj % i == 0)
            {
                pf[j].push_back(i);
                mj /= i;
            }
        }
    }
    vector<bool> res(q, true);
    for (int tr = 0; tr < 3; tr++)
    {
        vector<vector<uint_fast64_t>> hs(MAX, vector<uint_fast64_t>(3, 0));
        for (int i = 0; i < MAX; i++)
        {
            while (hs[i][0] == 0)
            { hs[i][0] = engine(); }
            while (hs[i][1] == 0 || hs[i][0] == hs[i][1])
            { hs[i][1] = engine(); }
            hs[i][2] = (hs[i][0] ^ hs[i][1]);
        }
        vector<int> bk(MAX, 0);
        vector<uint_fast64_t> rw(n + 1, 0);
        for (int i = 0; i < n; i++)
        {
            rw[i + 1] = rw[i];
            for (auto &nx: pf[a[i]])
            {
                rw[i + 1] ^= hs[nx][bk[nx] % 3];
                bk[nx]++;
            }
        }
        for (int i = 0; i < q; i++)
        {
            if (rw[l[i] - 1] != rw[r[i]])
            { res[i] = false; }
        }
    }
    for (int i = 0; i < q; i++)
    {
        if (res[i])
        { cout << "Yes\n"; }
        else
        { cout << "No\n"; }
    }
    return 0;
}