Test/CF/CF902-B.test.cpp

View this file on GitHub
Last update: 2025-05-29 15:37:34+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
Link: https://codeforces.com/contest/1876/problem/B
Link: https://codeforces.com/contest/1876/submission/321867982

Depends on

Code

// #define PROBLEM "https://codeforces.com/contest/1876/problem/B"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * CF902-B Effects of Anti Pimples
 * https://codeforces.com/contest/1876/submission/321867982
 */

#include "../../Src/Number/LinearSieve.hpp"
#include "atcoder/modint"

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <set>
using mint = atcoder::modint998244353;

const int N{ 100100 };
zawa::LinearSieve siv(N);

void solve() {
    int n; 
    std::cin >> n;
    std::vector<int> a(n);
    for (int i{} ; i < n ; i++) {
        std::cin >> a[i];
    }
    std::vector<std::pair<int, int>> max(n);
    for (int i{} ; i < n ; i++) {
        for (int j{i} ; j < n ; j += (i + 1)) {
            max[i].first = std::max(max[i].first, a[j]);
        }
        max[i].second = i + 1;
    }
    std::sort(max.begin(), max.end());
    std::reverse(max.begin(), max.end());

    std::vector<mint> p2(n + 1, mint{1});
    for (int i{} ; i < n ; i++) p2[i + 1] = p2[i] * mint{2};


    std::set<int> ng;
    mint ans{};
    for (int i{} ; i < n ; i++) {
        auto [val, idx]{ max[i] };
        auto div{ siv.divisor(idx) };
        int must{ (int)div.size() };
        for (auto d : div) if (ng.find(d) != ng.end()) must--;
        int t{ n - (int)ng.size() };
        ans += (p2[t] - p2[t - must]) * mint{val};
        for (auto d : div) ng.emplace(d);
    }
    std::cout << ans.val() << std::endl;
}

int main() {
#ifdef ONLINE_JUDGE
    solve();
#else
    std::cout << "Hello World" << std::endl;
#endif
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/modint: line -1: no such header