For a positive integer \(x\) and a prime \(p\), define the \(p\)-adic order of \(x\) as the number of times \(p\) occurs in the prime factorization of \(x\) (which equals the number of times \(p\) divides \(x\)). Also, let \(L_k\) be the lowest common divisor (LCM) of \(A\) except for \(A_k\).

The following holds:

For \(n\) positive integers \(x_1,\dots,x_n\) and any prime \(p\), the \(p\)-adic order of \(x_1,\dots,x_n\) coincides with the maximum \(p\)-adic order of \(x_1,\dots,x_n\).

Thus, when \(e_1(p)\geq e_2(p)\geq \cdots \geq e_N(p)\) is the sequence of \(p\)-adic orders of \(A_1,\dots,A_N\) sorted in descending order, the \(p\)-adic order of \(L_k\) is \(e_1(p)\) if the \(p\)-adic order of \(A_k\) is strictly less than \(e_1(p)\), and \(e_2(p)\) otherwise. Particularly, for a \(p\) that is not a prime factor of \(A_k\), the \(p\)-adic order of \(L_k\) is \(e_1(p)\).

Thus, the problem can be solved by the following procedure (we need to appropriately take modulus by \(998244353\)):

• Find the prime factorizations of \(A_1,\dots,A_N\).
• For each \(p\) that is a prime factor of any of \(A_1,\dots,A_N\), find \(e_1(p)\) and \(e_2(p)\).
• Let \(L\leftarrow\prod_{p}p^{e_1(p)}\), which equals the LCM of \(A_1,\dots,A_N\).
• For \(k=1,\dots,N\), do the following:
  • First, set \(L_k\leftarrow L\).
  • For each prime factor \(p\) of \(A_k\), if the \(p\)-adic order of \(A_k\) is strictly less than \(e_1(p)\), set \(L_k\leftarrow L_k / p^{e_1(p)-e_2(p)}\).

The prime factorizations of \(A_1,\dots,A_N\) can be found in \(O(\log M)\) time each by precalculating the minimum prime factor of each integer up to \(\max A(=:M)\) using the linear sieve (in \(O(M)\) time) or Eratosthenes’ sieve (in \(O(M\log\log M)\) time).
Also, prime factorizations by trial divisions can also be done within the time limit by limiting divisors to primes, or by implementing in a fast languages while carefully taking the constant factor into account.

Once the prime factorizations are obtained, the values of \(e_1(p)\) and \(e_2(p)\) can be obtained by using associative arrays. A rough estimation of the complexity is \(O\left(N\log M\left(\log N+\log \log M+\log\mathrm{MOD}\right)\right)\), which is sufficiently fast.

Sample code (C++):

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using mint = atcoder::modint998244353;
int main()
{
    const int M = 1e7;
    // Linear sieve
    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;
        // Compute e_1(p) and 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;
            }
        }
        
        // Find LCM(A_1,...,A_N)
        mint lcm = 1;
        for (auto &[p, e] : e1) lcm *= mint(p).pow(e);
        
        // Find the answer
        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];
        }
    }
}