提出 #73324549

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

const int N = 1e7 + 1, MOD = 998244353;
vector<int> lp(N), pr;
void linearSieve() {
    for (int i = 2; i < N; i++) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back(i);
        }
        for (int j = 0; i * pr[j] < N; j++) {
            lp[i * pr[j]] = pr[j];
            if (pr[j] == lp[i]) break;
        }
    }
}

int fp(int n, int p, int mod) {
    int res = 1;
    while (p) {
        if (p & 1) res = 1LL * res * n % mod;
        n = 1LL * n * n % mod;
        p >>= 1;
    }
    return res;
}

int modInv(int x, int mod) {
    return fp(x, mod - 2, mod);
} 

void O_O() {
    int n;
    cin >> n;

    vector<int> a(n);
    unordered_map<int, int> mp, mp2;
    for (int i = 0; i < n; i++) {
        cin >> a[i];

        int tmp = a[i], cur = lp[tmp], cnt = 0;
        if (a[i] == 1) continue;
        while (tmp) {
            if (lp[tmp] != cur) {
                if (mp[cur] == cnt) {
                    mp2[cur] = cnt;
                } else {
                    if (mp[cur] > cnt) mp2[cur] = max(mp2[cur] , cnt);
                    if (mp[cur] < cnt) mp2[cur] = max(mp2[cur] , mp[cur]), mp[cur] = cnt;
                }
                cur = lp[tmp], cnt = 0;
                if (!cur) break;
            }
            tmp /= lp[tmp], cnt++;
        }
    }

    int ans = 1;
    for (auto& [x, y] : mp) {
        ans = 1LL * ans * fp(x, y, MOD) % MOD;
    }

    for (int i = 0; i < n; i++) {
        int curAns = ans;
        int tmp = a[i], cur = lp[tmp], cnt = 0;
        if (a[i] != 1) {
            while (tmp) {
                if (lp[tmp] != cur) {
                    if (mp[cur] == cnt && mp2[cur] != cnt) {
                        curAns = 1LL * curAns * modInv(fp(cur, mp[cur], MOD), MOD) % MOD;
                        curAns = 1LL * curAns * fp(cur, mp2[cur], MOD) % MOD;
                    }
                    cur = lp[tmp], cnt = 0;
                    if (!cur) break;
                }
                tmp /= lp[tmp], cnt++;
            }
        }
        cout << curAns << ' ';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    linearSieve();

    int TC = 1;
    cin >> TC;
    while (TC--) {
        O_O();
        if (TC) cout << '\n';
    }

    return 0;
}

提出情報

ジャッジ結果