F Gcd Product

题意很短。主要介绍一种和 std 不同、比 std 思维量更低一些的做法。

定义 ，即 是三元组的集合。

定义 ，即两个三元组集合的积为另一个三元组的集合。

那么：通过打表可以发现， 具有积性。即对于互质的 有 。且当 为质数的幂次时，容易直接求出 。

于是只需要按线性筛的方法算出所有的 然后统计即可。实际上不需要保存所有的 ，只需要保存所有质数幂次的 的 即可（不然 MLE）。

时间复杂度应该是 。

#include <bits/stdc++.h>
#define MOD 998244353
using namespace std;
typedef pair<pair<int, int>, int> pa;
int n, a[500005], b[500005];
bool vis[500005] = {0};
int tot = 0, prime[250005];
int mintrace[500005];
int mindive[500005];
vector<pa> vec[500005], tmp[2];
inline int modadd(int x, int y){
    int t = x + y;
    return t >= MOD ? t - MOD: t;
}
int build_pk(int p, int k, int pk){
    vector<pa>& v = vec[pk];
    int tot = pk, res = 0;
    // for k' = k: 1
    v.push_back({{1, pk}, 1}), --tot;
    v.push_back({{pk, 1}, 1}), --tot;
    res = modadd(1ll * a[1] * b[pk] % MOD, 1ll * a[pk] * b[1] % MOD);

    long long j = p - 1;
    for (int i = k - 1; i >= 1; --i){
        pk /= p;
        // for k' = i: (p - 1) * p^(k - i - 1)
        v.push_back({{1, pk}, j}), tot -= j;
        v.push_back({{pk, 1}, j}), tot -= j;

        res = modadd(res, 1ll * a[1] * b[pk] % MOD * j % MOD);
        res = modadd(res, 1ll * a[pk] * b[1] % MOD * j % MOD);
        j *= p;
    }
    // for (1, 1)
    if (tot > 0){
        v.push_back({{1, 1}, tot});
        res = modadd(res, 1ll * a[1] * b[1] % MOD * tot % MOD);
    }
    return res;
}
void build_prod(vector<pa>& v1, vector<pa>& v2, vector<pa>& v){
    for (auto& p: v1)
        for (auto& p2: v2){
            int xa = p.first.first * p2.first.first;
            int ya = p.first.second * p2.first.second;
            int cntt = p.second * p2.second;
            v.push_back({{xa, ya}, cntt});
        }
}
int get_prod(int x){
    int cur = 0;
    tmp[1].clear();
    tmp[1].push_back({{1, 1}, 1});

    while (x > 1){
        int q = x / mintrace[x];
        // q: p^k
        tmp[cur].clear();
        build_prod(tmp[cur ^ 1], vec[q], tmp[cur]);
        cur ^= 1;
        x = mintrace[x];
    }

    int res = 0;
    cur ^= 1;
    for (auto& p: tmp[cur]){
        res = modadd(res, 1ll * a[p.first.first] * b[p.first.second] % MOD * p.second % MOD);
    }
    return res;
}
void solve(){
    // count for 1
    int ans = 1ll * a[1] * b[1] % MOD;
    vec[1].push_back({{1, 1}, 1});

    for (int i = 2; i <= n; ++i){
        if (!vis[i]){
            prime[++tot] = i;
            mintrace[i] = 1, mindive[i] = 1;
            ans ^= build_pk(i, 1, i);
        }
        for (int j = 1; j <= tot; ++j){
            if (prime[j] > n / i) break;
            int prod = i * prime[j];
            vis[prod] = true;
            if (i % prime[j] == 0){
                mintrace[prod] = mintrace[i];
                mindive[prod] = mindive[i] + 1;
                if (mintrace[i] == 1){
                    ans ^= build_pk(prime[j], mindive[prod], prod);
                } else {
                    ans ^= get_prod(prod);
                }
                break;
            } else {
                mintrace[prod] = i;
                ans ^= get_prod(prod);
            }
        }
    }

    printf("%d\n", ans);
}
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);

    solve();
    return 0;
}