Submission #73324549

Source Code Expand

#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;
}

Submission Info

Submission Time
Task E - Many LCMs
User Mariouma
Language C++23 (GCC 15.2.0)
Score 475
Code Size 2408 Byte
Status AC
Exec Time 366 ms
Memory 64816 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 475 / 475
Status
AC × 1
AC × 25
Set Name Test Cases
Sample 00_sample_01.txt
All 00_sample_01.txt, 01_large_t_01.txt, 01_large_t_02.txt, 01_large_t_03.txt, 02_large_n_01.txt, 02_large_n_02.txt, 02_large_n_03.txt, 03_prime_01.txt, 03_prime_02.txt, 03_prime_03.txt, 03_prime_04.txt, 03_prime_05.txt, 03_prime_06.txt, 04_small_prime_factor_01.txt, 04_small_prime_factor_02.txt, 04_small_prime_factor_03.txt, 04_small_prime_factor_04.txt, 04_small_prime_factor_05.txt, 04_small_prime_factor_06.txt, 05_large_value_01.txt, 05_large_value_02.txt, 05_large_value_03.txt, 05_large_value_04.txt, 05_large_value_05.txt, 05_large_value_06.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 59 ms 46712 KiB
01_large_t_01.txt AC 274 ms 46692 KiB
01_large_t_02.txt AC 280 ms 46564 KiB
01_large_t_03.txt AC 279 ms 46568 KiB
02_large_n_01.txt AC 313 ms 47608 KiB
02_large_n_02.txt AC 305 ms 48096 KiB
02_large_n_03.txt AC 309 ms 50528 KiB
03_prime_01.txt AC 142 ms 46560 KiB
03_prime_02.txt AC 324 ms 59460 KiB
03_prime_03.txt AC 320 ms 59256 KiB
03_prime_04.txt AC 320 ms 59308 KiB
03_prime_05.txt AC 216 ms 54760 KiB
03_prime_06.txt AC 217 ms 54768 KiB
04_small_prime_factor_01.txt AC 327 ms 46712 KiB
04_small_prime_factor_02.txt AC 247 ms 46568 KiB
04_small_prime_factor_03.txt AC 245 ms 46580 KiB
04_small_prime_factor_04.txt AC 246 ms 46612 KiB
04_small_prime_factor_05.txt AC 296 ms 46764 KiB
04_small_prime_factor_06.txt AC 297 ms 46688 KiB
05_large_value_01.txt AC 252 ms 46572 KiB
05_large_value_02.txt AC 144 ms 46564 KiB
05_large_value_03.txt AC 311 ms 52192 KiB
05_large_value_04.txt AC 366 ms 64816 KiB
05_large_value_05.txt AC 275 ms 50036 KiB
05_large_value_06.txt AC 224 ms 54812 KiB