Sum of Totient Function (verify/number_theory/totient_sum.test.cpp)

• View this file on GitHub
• Last update: 2026-01-05 01:05:39+01:00
• Problem: https://judge.yosupo.jp/problem/sum_of_totient_function

Depends on

• cp-algo/math/common.hpp
• cp-algo/number_theory/dirichlet.hpp
• cp-algo/number_theory/modint.hpp
• cp-algo/util/big_alloc.hpp

Code

// @brief Sum of Totient Function
#define PROBLEM "https://judge.yosupo.jp/problem/sum_of_totient_function"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <iostream>
//#include "blazingio/blazingio.min.hpp"
#include "cp-algo/number_theory/modint.hpp"
#include "cp-algo/number_theory/dirichlet.hpp"
#include "cp-algo/util/big_alloc.hpp"
#include <bits/stdc++.h>

using namespace std;
using namespace cp_algo::math;
using base = modint<998244353>;

void solve() {
    int64_t n;
    cin >> n;
    auto H = floors(n) | views::transform([](int64_t k) {
        return base(k) * base(k + 1) / 2;
    }) | ranges::to<cp_algo::big_vector<base>>();
    auto G = floors(n) | views::transform([](int64_t k) {
        return base(k);
    }) | ranges::to<cp_algo::big_vector<base>>();
    auto F = Dirichlet_div(H, G, n);
    cout << F.back() << "\n";
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 327, in update
    assert len(lines) == len(uncommented_lines)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError

Test cases

Env	Name	Status	Elapsed	Memory
g++	boundaryA_00	AC	55 ms	4 MB
g++	boundaryA_01	AC	120 ms	6 MB
g++	boundaryA_02	AC	158 ms	6 MB
g++	boundaryA_03	AC	171 ms	6 MB
g++	boundaryA_04	AC	111 ms	5 MB
g++	boundaryA_05	AC	101 ms	5 MB
g++	boundaryA_06	AC	161 ms	6 MB
g++	boundaryA_07	AC	195 ms	6 MB
g++	boundaryA_08	AC	79 ms	5 MB
g++	boundaryA_09	AC	113 ms	5 MB
g++	boundaryB_00	AC	55 ms	4 MB
g++	boundaryB_01	AC	120 ms	6 MB
g++	boundaryB_02	AC	158 ms	6 MB
g++	boundaryB_03	AC	171 ms	6 MB
g++	boundaryB_04	AC	110 ms	5 MB
g++	boundaryB_05	AC	101 ms	5 MB
g++	boundaryB_06	AC	161 ms	6 MB
g++	boundaryB_07	AC	197 ms	6 MB
g++	boundaryB_08	AC	79 ms	5 MB
g++	boundaryB_09	AC	113 ms	5 MB
g++	example_00	AC	4 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	example_02	AC	4 ms	4 MB
g++	handmade_00	AC	4 ms	4 MB
g++	handmade_01	AC	4 ms	4 MB
g++	handmade_02	AC	4 ms	4 MB
g++	handmade_03	AC	4 ms	4 MB
g++	max_00	AC	197 ms	6 MB
g++	max_01	AC	196 ms	6 MB
g++	max_02	AC	196 ms	6 MB
g++	max_03	AC	196 ms	6 MB
g++	max_04	AC	195 ms	6 MB
g++	max_05	AC	197 ms	6 MB
g++	max_06	AC	197 ms	6 MB
g++	max_07	AC	196 ms	6 MB
g++	max_08	AC	196 ms	6 MB
g++	max_09	AC	196 ms	6 MB
g++	random_00	AC	56 ms	4 MB
g++	random_01	AC	121 ms	6 MB
g++	random_02	AC	159 ms	6 MB
g++	random_03	AC	173 ms	6 MB
g++	random_04	AC	111 ms	5 MB
g++	random_05	AC	101 ms	5 MB
g++	random_06	AC	161 ms	6 MB
g++	random_07	AC	195 ms	6 MB
g++	random_08	AC	79 ms	5 MB
g++	random_09	AC	113 ms	5 MB
g++	small_00	AC	4 ms	4 MB

Back to top page