This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/sum_of_totient_function" #include <iostream> #include <atcoder/modint> using mint = atcoder::modint998244353; #include "library/number/sum_of_totient_function.hpp" int main() { uint64_t n; std::cin >> n; suisen::SumOfTotientFunction<mint> sum(n); std::cout << sum().val() << std::endl; return 0; }
#line 1 "test/src/number/sum_of_totient_function/sum_of_totient_function.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/sum_of_totient_function" #include <iostream> #include <atcoder/modint> using mint = atcoder::modint998244353; #line 1 "library/number/sum_of_totient_function.hpp" #include <cstdint> #include <cmath> #include <numeric> #include <vector> namespace suisen { // reference: https://yukicoder.me/wiki/sum_totient template <typename T> struct SumOfTotientFunction { SumOfTotientFunction() : SumOfTotientFunction(1) {} SumOfTotientFunction(uint64_t n) : _n(n), _sz_s(threshold(_n) + 1), _sz_l(_n / _sz_s + 1), _dp_s(_sz_s), _dp_l(_sz_l) { std::vector<uint32_t> phi(_sz_s); std::iota(phi.begin(), phi.end(), 0); for (uint32_t p = 2; p < _sz_s; ++p) { if (phi[p] != p) continue; for (uint32_t q = p; q < _sz_s; q += p) phi[q] = phi[q] / p * (p - 1); } for (uint32_t i = 1; i < _sz_s; ++i) _dp_s[i] = phi[i] + _dp_s[i - 1]; for (uint32_t d = _sz_l - 1; d > 0; --d) { uint64_t i = _n / d; // avoid overflow if (i & 1) _dp_l[d] = (i + 1) / 2, _dp_l[d] *= i; else _dp_l[d] = i / 2, _dp_l[d] *= i + 1; for (uint64_t l = 2; l <= i;) { uint64_t q = i / l, r = i / q; _dp_l[d] -= (q < _sz_s ? _dp_s[q] : _dp_l[d * l]) * (r - l + 1); l = r + 1; } } } T operator()(uint64_t denominator = 1) const { uint64_t q = _n / denominator; return q < _sz_s ? _dp_s[q] : _dp_l[_n / (q + 1) + 1]; } private: uint64_t _n; uint32_t _sz_s, _sz_l; std::vector<T> _dp_s; std::vector<T> _dp_l; // q = (n / log log n) ^ (2 / 3) static uint32_t threshold(uint64_t n) { double t = std::cbrt(n / std::max(1., std::log(std::max(1., std::log(n))))); return uint32_t(std::max(1., t * t)); } }; } // namespace suisen #line 9 "test/src/number/sum_of_totient_function/sum_of_totient_function.test.cpp" int main() { uint64_t n; std::cin >> n; suisen::SumOfTotientFunction<mint> sum(n); std::cout << sum().val() << std::endl; return 0; }