提出 #73318301

---

ソースコード 拡げる

#include <stdio.h>

#define MOD 998244353
#define MAXA 10000001
#define MAXN 200005

int min_prime[MAXA];
int max1[MAXA], max2[MAXA], count1[MAXA];
int A[MAXN];

// Precompute smallest prime factor for fast factorization
void sieve() {
    for (int i = 2; i < MAXA; i++) {
        if (min_prime[i] == 0) {
            for (int j = i; j < MAXA; j += i)
                if (min_prime[j] == 0) min_prime[j] = i;
        }
    }
}

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

void solve() {
    int N;
    scanf("%d", &N);
    
    // Track which primes were seen to reset arrays efficiently
    int seen_primes[MAXN * 10], sp_ptr = 0;

    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
        int temp = A[i];
        while (temp > 1) {
            int p = min_prime[temp];
            int count = 0;
            while (temp % p == 0) {
                temp /= p;
                count++;
            }
            
            if (max1[p] == 0) seen_primes[sp_ptr++] = p;

            if (count > max1[p]) {
                max2[p] = max1[p];
                max1[p] = count;
                count1[p] = 1;
            } else if (count == max1[p]) {
                count1[p]++;
            } else if (count > max2[p]) {
                max2[p] = count;
            }
        }
    }

    // Calculate Global LCM
    long long total_lcm = 1;
    for (int i = 0; i < sp_ptr; i++) {
        total_lcm = (total_lcm * power(seen_primes[i], max1[seen_primes[i]])) % MOD;
    }

    // Modular Inverse for division (if needed) is tricky because of MOD. 
    // Instead, calculate change for each k.
    for (int i = 0; i < N; i++) {
        long long current_lcm = total_lcm;
        int temp = A[i];
        while (temp > 1) {
            int p = min_prime[temp];
            int count = 0;
            while (temp % p == 0) {
                temp /= p;
                count++;
            }
            // If this element was the unique provider of the max power
            if (count == max1[p] && count1[p] == 1) {
                // Remove p^max1 and multiply by p^max2
                long long inv = power(power(p, max1[p]), MOD - 2);
                current_lcm = (current_lcm * inv) % MOD;
                current_lcm = (current_lcm * power(p, max2[p])) % MOD;
            }
        }
        printf("%lld%c", current_lcm, (i == N - 1 ? '\n' : ' '));
    }

    // Clean up global arrays for next test case
    for (int i = 0; i < sp_ptr; i++) {
        int p = seen_primes[i];
        max1[p] = max2[p] = count1[p] = 0;
    }
}

int main() {
    sieve();
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

提出情報

ジャッジ結果