提出 #73310362

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
using namespace std;

const int MAX_A = 10000000;
const long long MOD = 998244353;

vector<int> spf(MAX_A + 1);

void build_spf() {
    for (int i = 1; i <= MAX_A; ++i)
        spf[i] = i;
    for (int i = 2; i * i <= MAX_A; ++i) {
        if (spf[i] == i) {
            for (int j = i * i; j <= MAX_A; j += i) {
                if (spf[j] == j)
                    spf[j] = i;
            }
        }
    }
}

vector<pair<int, int>> factorize(int x) {
    vector<pair<int, int>> factors;
    while (x > 1) {
        int p = spf[x];
        int cnt = 0;
        while (spf[x] == p) {
            cnt++;
            x /= p;
        }
        factors.emplace_back(p, cnt);
    }
    return factors;
}

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    build_spf();

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;
        vector<int> A(N);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
        }

        unordered_map<int, int> max_exp, second_max, count_max;

        for (int x : A) {
            auto fac = factorize(x);
            for (auto [p, e] : fac) {
                if (e > max_exp[p]) {
                    second_max[p] = max_exp[p];
                    max_exp[p] = e;
                    count_max[p] = 1;
                } else if (e == max_exp[p]) {
                    count_max[p]++;
                } else if (e > second_max[p]) {
                    second_max[p] = e;
                }
            }
        }

        long long global_lcm = 1;
        for (auto& [p, e] : max_exp) {
            global_lcm = (global_lcm * mod_pow(p, e, MOD)) % MOD;
        }

        vector<long long> ans(N);
        for (int k = 0; k < N; ++k) {
            long long res = global_lcm;
            auto fac = factorize(A[k]);
            for (auto [p, e] : fac) {
                if (e == max_exp[p] && count_max[p] == 1) {
                    int new_e = second_max[p];
                    int diff = e - new_e;
                    long long divisor = mod_pow(p, diff, MOD);
                    long long inv_div = mod_pow(divisor, MOD - 2, MOD);
                    res = (res * inv_div) % MOD;
                }
            }
            ans[k] = res;
        }

        for (int i = 0; i < N; ++i) {
            if (i) cout << " ";
            cout << ans[i];
        }
        cout << "\n";
    }

    return 0;
}

提出情報

ジャッジ結果