Submission #67786677

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

int add(int a, int b) {
    return a >= MOD - b ? a - MOD + b : a + b;
}

int sub(int a, int b) {
    return a >= b ? a - b : a - b + MOD;
}

int mul(int a, int b) {
    return (1ll * a * b) % MOD;
}

int pw(int x, int n) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            x = mul(x, x);
            n /= 2;
        } else {
            res = mul(res, x);
            --n;
        }
    }
    return res;
}

template<typename... Tail>
int mul(int a, Tail... tail) {
    return mul(a, mul(tail...));
}

template<typename... Tail>
int add(int a, Tail... tail) {
    return add(a, add(tail...));
}

vector<int> fact, invf;

void init_fact(int n = 2'000'000) {
    int val = fact.size();
    if (val >= n) return;
    if (val * 2 > n) n = val * 2;
    fact.resize(n);
    invf.resize(n);
    if (val == 0) {
        fact[0] = 1;
        invf[0] = 1;
        val = 1;
    }
    for (int i = val; i < n; ++i) {
        fact[i] = mul(fact[i - 1], i);
    }
    invf[n - 1] = pw(fact[n - 1], MOD - 2);
    for (int i = n - 1; i > val; --i) {
        invf[i - 1] = mul(invf[i], i);
    }
}

int inv(int n) {
    if (n > 20'000'000) {
        return pw(n, MOD - 2);
    }
    init_fact(n + 1);
    return mul(invf[n], fact[n - 1]);
}

int C(int n, int k) {
    init_fact(n + 1);
    if (k == -1) {
        if (n == -1) return 1;
        return 0;
    }
    if (k < 0) return 0;
    if (n < 0) {
        int res = C(k - n - 1, k);
        if (k & 1) return sub(0, res);
        return res;
    }
    if (k > n) return 0;
    return mul(fact[n], invf[k], invf[n - k]);
}

const int MAXA = 2e5 + 100;
int have[MAXA];
int cyc[MAXA];
int icyc[MAXA];
vector<int> divs[MAXA];

void solve_() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    have[1] = 1;
    int ans = 1;
    for (int i = 0; i < n; ++i) {
        for (int d : divs[a[i]]) {
            if (!have[d]) {
                have[d] = true;
                ans = mul(ans, cyc[d]);
            }
        }
        cout << ans << "\n";
    }
}

/// #define MULTITEST

signed main() {
#ifdef LOCAL
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#endif

    for (int i = 1; i < MAXA; ++i) {
        cyc[i] = sub(pw(10, i), 1);
        icyc[i] = inv(cyc[i]);
    }
    for (int i = 1; i < MAXA; ++i) {
        for (int j = i * 2; j < MAXA; j += i) {
            cyc[j] = mul(cyc[j], icyc[i]);
            icyc[j] = mul(icyc[j], cyc[i]);
        }
    }
    for (int i = 1; i < MAXA; ++i) {
        for (int j = i; j < MAXA; j += i) {
            divs[j].push_back(i);
        }
    }

    int tst = 1;
#ifdef MULTITEST
    cin >> tst;
#endif // MULTITEST
    while (tst--) {
        solve_();
    }
    return 0;
}

Submission Info

Judge Result