题目传送门

sol1：老实做，预处理出所有2到1e5的素数，对所有数进行分解质因数，然后对比因子个数。感觉有点卡常，用了快读然后多次优化之后才过的，map也用上了。

素数筛，快速分解质因数

#include "bits/stdc++.h"

using namespace std;

typedef long long LL;

const int MAXN = 1e5 + ;

bool v[MAXN];

map<int, int> mp;

int p[MAXN], pos;

int a[MAXN], b[MAXN];

LL ca[MAXN], cb[MAXN];

void init() {

    for (int i = ; i <= 1e5; i++) {

        if (v[i] == false) {

            p[++pos] = i;

            mp[i] = pos;

            for (int j = i << ; j <= 1e5; j += i)

                v[j] = true;

        }

    }

}

inline int read() {

    int n = ;

    char c = getchar();

    while (c < '' || c > '') c = getchar();

    while (c >= '' && c <= '') {

        n = n *  + (c ^ '');

        c = getchar();

    }

    return n;

}

void fun(int k, int c, LL* a) {

    for (int i = ; v[k]; i++) {

        while (k % p[i] == ) {

            k /= p[i];

            a[i] += c;

        }

    }

    if (k != ) a[mp[k]] += c;

}

int main() {

    init();

    int t, n, m, k;

    t = read();

    while (t--) {

        n = read(), m = read();

        memset(ca, , sizeof(LL) * (pos + ));

        memset(cb, , sizeof(LL) * (pos + ));

        for (int i = ; i <= n; i++) a[i] = read();

        for (int i = ; i <= m; i++) b[i] = read();

        sort(a + , a +  + n);

        sort(b + , b +  + m);

        k = ;

        for (int i = ; i <= a[n]; i++) {

            while (i > a[k]) k++;

            fun(i, n - k + , ca);

        }

        k = ;

        for (int i = ; i <= b[m]; i++) {

            while (i > b[k]) k++;

            fun(i, m - k + , cb);

        }

        bool ok = true;

        for (int i = ; i <= pos; i++) {

            if (ca[i] != cb[i]) {

                ok = false;

                break;

            }

        }

        if (ok) puts("equal");

        else puts("unequal");

    }

    return ;

}

sol2：题解上说用哈希。虽然一开始也有想到哈希，但是怕哈希冲突，没怎么在比赛中用过哈希，没有哈希的意识。知道用哈希之后代码就信手拈来了，不过还是产生了一次哈希冲突，不要用1e9 + 7这种特殊素数，决定还是使用2147483587（int范围第二大的素数，怕最大的会被卡）。

哈希

#include "bits/stdc++.h"

using namespace std;

const int MAXN = 1e5 + ;

const int MOD = ;

int a[MAXN], b[MAXN];

int quick_pow(int n, int k) {

    int ans = ;

    while (k) {

        if (k & ) ans = 1LL * ans * n % MOD;

        n = 1LL * n * n % MOD;

        k >>= ;

    }

    return ans;

}

int main() {

    int t, n, m, k;

    scanf("%d", &t);

    while (t--) {

        scanf("%d%d", &n, &m);

        for (int i = ; i <= n; i++)

            scanf("%d", &a[i]);

        for (int i = ; i <= m; i++)

            scanf("%d", &b[i]);

        sort(a + , a +  + n);

        sort(b + , b +  + m);

        int ha = , hb = ;

        k = ;

        for (int i = ; i <= a[n]; i++) {

            while (i > a[k]) k++;

            ha = 1LL * ha * quick_pow(i, n - k + ) % MOD;

        }

        k = ;

        for (int i = ; i <= b[m]; i++) {

            while (i > b[k]) k++;

            hb = 1LL * hb * quick_pow(i, m - k + ) % MOD;

        }

        if (ha == hb) puts("equal");

        else puts("unequal");

    }

    return ;

}

哈希

牛客-小w的a=b问题

题目传送门