Submission #67803507

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i ++)
#define per(i, s, t) for(int i = (s); i >= (t); i --)
template<typename T, typename T2>
inline void chmin(T &x, T2 &&y) { x = min(x, y); }
template<typename T, typename T2>
inline void chmax(T &x, T2 &&y) { x = max(x, y); }
typedef long long ll;

ll lcm(ll x, ll y) { return x / __gcd(x, y) * y; }
ll lcm(vector<ll> x)
{
    ll ans = x[0];
    for(ll i : x) ans = lcm(ans, i);
    return ans;
}

ll R(int x)
{
    ll ans = 0;
    rep(i, 1, x) ans = ans * 10 + 1;
    return ans;
}

const int N = 2e5 + 5, p = 998244353;

int r[N];
ll qpow(ll a, ll b)
{
    if(!b) return 1;
    return ((b & 1) ? a : 1ll) * qpow(a * a % p, b >> 1) % p;
}

vector<int> d[N];

int cnt[N];
int cd[N];

void add(int x, int v)
{
    cnt[x] = (cnt[x] + v) % (p - 1);
    for(int i : d[x]) cd[i] = (cd[i] + v) % (p - 1);
}
int qry(int x)
{
    return cd[x];
}

int a[N];

signed main()
{
    r[1] = 1; rep(i, 2, N - 1) r[i] = (10ll * r[i - 1] + 1) % p;
    rep(i, 1, N - 1) for(int j = i; j < N; j += i) d[j].push_back(i);
    
    // vector<pair<int, int>> cc;
    // int s = 0;
    // rep(i, 1, N - 1) { int cnt = 0; for(int j : d[i]) cnt += d[i / j].size(); cc.push_back({cnt, i}); s += cnt; }
    // cout << s;

    ios::sync_with_stdio(0);cin.tie(0);
    int n; cin >> n;
    int ans = 1;
    
    bool vis[N] = {};
    rep(i, 1, n)
    {
        int x; cin >> x;
        if(vis[x]) goto end;
        vis[x] = 1;
        for(int j : d[x])
        {
            a[j] = -qry(j);
        }
        // for(int j : d[x])
        //     cout << j << " " << a[j] << endl;
        per(j, d[x].size() - 1, 0)
        {
            int v = d[x][j];
            for(int k : d[x / v]) if(k > 1)
            {
                a[v] = (a[v] - a[v * k]) % (p - 1);
            }
        }
        a[x] ++;
        for(int j : d[x])
        {
            // cout << j << " " << a[j] << endl;
            ans = 1ll * ans * qpow(r[j], (a[j] % (p - 1) + (p - 1)) % (p - 1)) % p;
            add(j, a[j]);
        }
        end:
        cout << ans << "\n";
    }

    return 0;
}

Submission Info

Judge Result