正整数 \(x\) および素数 \(p\) に対して \(x\) の素因数分解で \(p\) が現れる個数（\(x\) が \(p\) で割り切れる回数に等しい）を \(x\) の \(p\) の指数と呼ぶことにします。 また \(A\) から \(A_k\) を除いた \(N-1\) 要素の最小公倍数を \(L_k\) とします。

以下が成り立ちます。

\(n\) 個の正整数 \(x_1,\dots,x_n\) および任意の素数 \(p\) に対し、\(x_1,\dots,x_n\) の最小公倍数の \(p\) の指数は \(x_1,\dots,x_n\) の \(p\) の指数の最大値と一致する。

これより \(A_1,\dots,A_N\) の \(p\) の指数を降順に並び替えた列を \(e_1(p)\geq e_2(p)\geq \cdots \geq e_N(p)\) とすると、\(L_k\) の \(p\) の指数は \(A_k\) の \(p\) の指数が \(e_1(p)\) 未満のとき \(e_1(p)\)、そうでないとき \(e_2(p)\) になります。特に \(A_k\) の素因数でない \(p\) については \(L_k\) の \(p\) の指数は \(e_1(p)\) です。

したがってこの問題は以下の流れで解くことができます（適宜 \(998244353\) で割ったあまりを計算する必要があります）。

• \(A_1,\dots,A_N\) を素因数分解する。
• \(A_1,\dots,A_N\) いずれかの素因数であるような素数 \(p\) について \(e_1(p),e_2(p)\) の値を求める。
• \(L\leftarrow\prod_{p}p^{e_1(p)}\) とする。これは \(A_1,\dots,A_N\) の最小公倍数に等しい。
• \(k=1,\dots,N\) に対して以下を行う。
  • はじめ \(L_k\leftarrow L\) とする。
  • \(A_k\) の素因数 \(p\) に対し、\(A_k\) の \(p\) の指数が \(e_1(p)\) 未満ならば \(L_k\leftarrow L_k / p^{e_1(p)-e_2(p)}\) とする。

\(A_1,\dots,A_N\) の素因数分解については、\(\max A(=:M)\) 以下の正整数それぞれに対して最小の素因数を線形篩（\(O(M)\) 時間）やエラトステネスの篩（\(O(M\log\log M)\) 時間）で前計算しておくことで、一つあたり \(O(\log M)\) 時間で素因数分解できます。
また試し割りによる素因数分解でも、試し割りする数を素数に限定する、あるいは高速な言語で定数倍に注意することで時間制限に間に合わせることができます。

素因数分解以外の部分について、\(e_1(p),e_2(p)\) の値は連想配列を用いると簡単に管理できます。 計算量に関しては大雑把に評価しても \(O\left(N\log M\left(\log N+\log \log M+\log\mathrm{MOD}\right)\right)\) 時間などであり、十分高速です。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using mint = atcoder::modint998244353;
int main()
{
    const int M = 1e7;
    // 線形篩
    vector<int> lpf(M + 1);
    iota(lpf.begin(), lpf.end(), 0);
    vector<int> primes;
    for (int x = 2; x <= M; x++)
    {
        if (lpf[x] == x) primes.push_back(x);
        for (auto p : primes) {
            if ((int64_t)p * x > M || p > lpf[x]) break;
            lpf[p * x] = p;
        }
    }
    int T;
    cin >> T;
    while (T--)
    {
        int N;
        cin >> N;
        vector<int> A(N);
        for (int i = 0; i < N; i++) cin >> A[i];
        
        // e1[p]=e_1(p), e2[p]=e_2(p)
        map<int, int> e1, e2;
        // e_1(p), e_2(p) を計算
        for (int i = 0; i < N; i++)
        {
            int x = A[i];
            while (x > 1)
            {
                int p = lpf[x], e = 0;
                while (x % p == 0) x /= p, e++;
                if (e > e1[p])
                    e2[p] = e1[p], e1[p] = e;
                else if (e > e2[p])
                    e2[p] = e;
            }
        }
        
        // LCM(A_1,...,A_N) を計算
        mint lcm = 1;
        for (auto &[p, e] : e1) lcm *= mint(p).pow(e);
        
        // 答えを計算
        for (int i = 0; i < N; i++)
        {
            mint ans = lcm;
            int x = A[i];
            while (x > 1)
            {
                int p = lpf[x], e = 0;
                while (x % p == 0) x /= p, e++;
                if (e == e1[p]) ans /= mint(p).pow(e1[p] - e2[p]);
            }
            cout << ans.val() << " \n"[i + 1 == N];
        }
    }
}