cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/CF/CF1070-F.test.cpp

Depends on

Code

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

/*
 * Codeforces Round1070 (Div. 2) F. Omega Numbers
 * https://codeforces.com/contest/2176/submission/357801306
 */

#include "../../Src/Number/LinearSieve.hpp"
#include "../../Src/Utility/GreyCode.hpp"
#include "atcoder/modint"
using mint = atcoder::modint998244353;
#include <array>
#include <iostream>
using namespace std;
using namespace zawa;
const int MAX = 11;
using Item = array<long long, MAX>;
Item zero() {
    Item res;
    res.fill(0);
    return res;
}
struct PD {
    using Element = int;
    static Element identity() {
        return 1;
    }
    static void add(Element& a, Element b) {
        a *= b;
    }
    static void remove(Element& a, Element b) {
        a /= b;
    }
};
void solve() {
    int N, K;
    cin >> N >> K;
    LinearSieve siv(N);
    vector<Item> cnt(N + 1, zero());
    Item ans = zero();
    auto primes = [&](int a) -> vector<int> {
        vector<int> res;
        for (auto d : siv.factorize(a))
            res.push_back(d.factor());
        return res;
    };
    auto calc = [&](int a) {
        vector<int> p = primes(a);
        vector<int> d = EnumerateSubsetProduct<PD>(p);
        vector<Item> cur(1 << ssize(p));
        for (int b = 0 ; b < (1 << ssize(p)) ; b++)
            cur[b] = cnt[d[b]];
        for (int i = 0 ; i < ssize(p) ; i++)
            for (int b = 0 ; b < (1 << ssize(p)) ; b++)
                if (b & (1 << i))
                    for (int j = 0 ; j < MAX ; j++)
                        cur[b ^ (1 << i)][j] -= cur[b][j];
        for (int b = 0 ; b < (1 << ssize(p)) ; b++)
            for (int i = 0 ; i < MAX ; i++) {
                int key = i + ssize(p) - popcount<unsigned>(b);
                if (0 <= key and key < MAX)
                    ans[key] += cur[b][i];
            }
    };
    auto add = [&](int a) {
        vector<int> p = primes(a);
        int m = 1;
        for (int i = 0 ; i < ssize(p) ; i++)
            m *= p[i];
        for (int d : siv.divisor(m))
            cnt[d][p.size()]++;
    };
    for (int i = 0 ; i < N ; i++) {
        int a;
        cin >> a;
        calc(a);
        add(a);
    }
    mint res = 0;
    for (int i = 0 ; i < MAX ; i++)
        res += mint::raw(i).pow(K) * ans[i];
    cout << res.val() << '\n';
}
int main() {
#ifdef ONLINE_JUDGE
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--)
        solve();
#else
    cout << "Hello World\n";
#endif
}
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/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.12.13/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/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.12.13/x64/lib/python3.12/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
Back to top page