Submission #67788709

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define overload4(a, b, c, d, name, ...) name
#define rep1(n) for (ll i = 0; i < n; ++i)
#define rep2(i, n) for (ll i = 0; i < n; ++i)
#define rep3(i, a, b) for (ll i = a; i < b; ++i)
#define rep4(i, a, b, c) for (ll i = a; i < b; i += c)
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
void solve();
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++) solve();
    return 0;
}
#include <atcoder/modint>
using mint = atcoder::modint998244353;
void solve() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    constexpr ll maxA = 2e5 + 10;
    vector<vector<ll>> factors(maxA);
    for (ll i = 1; i < maxA; i++) {
        for (ll j = i; j < maxA; j += i) {
            factors[j].push_back(i);
        }
    }
    vector<mint> pow10(maxA, 1), Fd(maxA);
    rep(i, 1, maxA) pow10[i] = pow10[i - 1] * 10;
    Fd[1] = 9;
    rep(i, 2, maxA) {
        Fd[i] = pow10[i] - 1;
        mint val = 1;
        for (auto f : factors[i]) {
            if (f == i) continue;
            val *= Fd[f];
        }
        Fd[i] /= val;
    }
    vector<ll> used(maxA), used2(maxA);
    mint res = 1;
    for (auto x : a) {
        if (used[x]) {
            cout << res.val() << '\n';
            continue;
        }
        used[x] = 1;
        mint val = 1;
        for (auto f : factors[x]) {
            if (f == 1) continue;
            if (used2[f]) continue;
            used2[f] = 1;
            val *= Fd[f];
        }
        res *= val;
        cout << res.val() << '\n';
    }
}

Submission Info

Judge Result