1876B - Effects of Anti Pimples - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+37;
int mod = 998244353;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); 

    int n; cin >> n;

    vector<int> a(n);
    vector<int> b((int)1e5+37, 0);

    for(auto &i: a) cin >> i;

    for(int i=0; i<n; i++){
        int ma = a[i];
        for(int l=i; l<n; l+=(i+1)){
            ma=max(ma, a[l]);
        }

        b[ma]++;
    }
    vector<int> p(n+5);
    p[0]=1;

    for(int i=1; i<n+5; i++){
        p[i] = p[i-1]*2;
        p[i] %= mod;
    }

    int el=1, ans = 0;
    for(int i=0; i<1e5+37; i++){
        if(i!=0)
        b[i]+=b[i-1];   

        b[i]%=mod;

        int val = p[b[i]]-((i==0)?0:p[b[i-1]]);
        val %= mod; val+= mod; val%=mod;

        ans+=(val*i)%mod;
        ans %= mod;

      //  cout << val << "\n";
    }

    cout << ans;

}