提出 #67792244

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#include <atcoder/modint>
using mint = atcoder::modint998244353;

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

    // input
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];
    
    // 約数を列挙する
    const int L = 200'200;
    vector<vector<int>> table(L);
    rep(i, 1, L) {
        for (int j = i; j < L; j += i){
            table[j].push_back(i);
        }
    }
    
    // R を求める
    vector<mint> R(L), R_inv(L);
    {
        mint tmp = 1;
        rep(i, 1, L){
            R[i] = tmp;
            tmp *= 10;
            tmp += 1;
            R_inv[i] = R[i].inv();
        }
    }
    
    // C[i] = 1 -> A[j] が i の倍数となるような j が存在する
    vector<int> C(L);
    C[1] = 1;
    mint ans = 1;
    rep(i, 0, N){
        // 以前出たことない時だけ探索
        if (C[A[i]] == 0){
            int a = A[i];
            vector<int> p(table[a].size());
            rep(j, 0, table[a].size()) if (C[table[a][j]] == 0) p[j] = 1;
            for (int j = (int)table[a].size() - 1; j >= 0; j--){
                // 約数包除原理
                rep(k, j + 1, table[a].size()){
                    if (table[a][k] % table[a][j] == 0) p[j] -= p[k];
                }
                ans *= (p[j] < 0 ? R_inv[table[a][j]].pow(-p[j]) : R[table[a][j]].pow(p[j]));
            }
            for (auto x : table[a]) C[x] = 1;
        }
        cout << ans.val() << "\n";
    }
}

提出情報

ジャッジ結果