Submission #73322291

---

Source Code Expand

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    iterator = iter(data)

    MAX_A = 10000001
    MOD = 998244353

    spf = list(range(MAX_A))
    for i in range(2, int(MAX_A**0.5) + 1):
        if spf[i] == i:
            for j in range(i * i, MAX_A, i):
                if spf[j] == j:
                    spf[j] = i

    try:
        t_str = next(iterator)
        T = int(t_str)
    except StopIteration:
        return

    out = []

    for _ in range(T):
        N = int(next(iterator))
        A = [int(next(iterator)) for _ in range(N)]

        primes = {} 
        
        objects = []
        
        for x in A:
            local_map = {}
            while x > 1:
                p = spf[x]
                cnt = 0
                while x % p == 0:
                    x //= p
                    cnt += 1
                local_map[p] = cnt
                
                if p not in primes:
                    primes[p] = [cnt, 0, 1]
                else:
                    rec = primes[p]
                    if cnt > rec[0]:
                        rec[1] = rec[0]
                        rec[0] = cnt
                        rec[2] = 1
                    elif cnt == rec[0]:
                        rec[2] += 1
                    elif cnt > rec[1]:
                        rec[1] = cnt
            objects.append(local_map)

        base_lcm = 1
        for p, (mx, mx2, c) in primes.items():
            base_lcm = base_lcm * pow(p, mx, MOD) % MOD

        ans = []
        for i in range(N):
            val = base_lcm
            for p, cnt in objects[i].items():
                rec = primes[p]
                if cnt == rec[0] and rec[2] == 1:
                    inv = pow(pow(p, rec[0] - rec[1], MOD), MOD - 2, MOD)
                    val = val * inv % MOD
            ans.append(str(val))
        
        out.append(" ".join(ans))

    print("\n".join(out))

if __name__ == '__main__':
    solve()

Submission Info

Judge Result