sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/sum_of_totient_function" #include <bits/stdc++.h> #include "../../math/modint.hpp" #include "../../math/number-theory/euler_totient.hpp" using namespace std; using mint = Modint<998244353>; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); long long N; cin >> N; auto [small, large] = totient_summatory_table<mint>(N); mint ans = large[1]; cout << ans << endl; }
#line 1 "test/yosupo/sum_of_totient_function.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/sum_of_totient_function" #include <bits/stdc++.h> #line 4 "math/modint.hpp" /** * @brief Mod int */ template <int m> class Modint { using mint = Modint; static_assert(m > 0, "Modulus must be positive"); public: static constexpr int mod() { return m; } constexpr Modint(long long y = 0) : x(y >= 0 ? y % m : (y % m + m) % m) {} constexpr int val() const { return x; } constexpr mint& operator+=(const mint& r) { if ((x += r.x) >= m) x -= m; return *this; } constexpr mint& operator-=(const mint& r) { if ((x += m - r.x) >= m) x -= m; return *this; } constexpr mint& operator*=(const mint& r) { x = static_cast<int>(1LL * x * r.x % m); return *this; } constexpr mint& operator/=(const mint& r) { return *this *= r.inv(); } constexpr bool operator==(const mint& r) const { return x == r.x; } constexpr mint operator+() const { return *this; } constexpr mint operator-() const { return mint(-x); } constexpr friend mint operator+(const mint& l, const mint& r) { return mint(l) += r; } constexpr friend mint operator-(const mint& l, const mint& r) { return mint(l) -= r; } constexpr friend mint operator*(const mint& l, const mint& r) { return mint(l) *= r; } constexpr friend mint operator/(const mint& l, const mint& r) { return mint(l) /= r; } constexpr mint inv() const { int a = x, b = m, u = 1, v = 0; while (b > 0) { int t = a / b; std::swap(a -= t * b, b); std::swap(u -= t * v, v); } return mint(u); } constexpr mint pow(long long n) const { mint ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend std::ostream& operator<<(std::ostream& os, const mint& r) { return os << r.x; } friend std::istream& operator>>(std::istream& is, mint& r) { long long t; is >> t; r = mint(t); return is; } private: int x; }; #line 4 "math/number-theory/euler_totient.hpp" long long euler_totient(long long n) { long long ret = n; if (n % 2 == 0) { ret -= ret / 2; while (n % 2 == 0) n /= 2; } for (long long i = 3; i * i <= n; i += 2) { if (n % i == 0) { ret -= ret / i; while (n % i == 0) n /= i; } } if (n != 1) ret -= ret / n; return ret; } std::vector<int> euler_totient_table(int n) { std::vector<int> ret(n + 1); std::iota(ret.begin(), ret.end(), 0); for (int i = 2; i <= n; ++i) { if (ret[i] == i) { for (int j = i; j <= n; j += i) { ret[j] = ret[j] / i * (i - 1); } } } return ret; } template <typename mint> std::pair<std::vector<mint>, std::vector<mint>> totient_summatory_table( long long n) { if (n == 0) return {{0}, {0}}; const int b = std::min(n, (long long)1e4); std::vector<mint> small(n / b + 1), large(b + 1); std::vector<int> totient(n / b + 1); std::iota(totient.begin(), totient.end(), 0); for (int i = 2; i <= n / b; ++i) { if (totient[i] != i) continue; for (int j = i; j <= n / b; j += i) { totient[j] = totient[j] / i * (i - 1); } } for (int i = 0; i < n / b; ++i) small[i + 1] = small[i] + totient[i + 1]; for (int i = 1; i <= b; ++i) { mint k = n / i; large[i] = k * (k + 1) / 2; } for (long long i = b; i >= 1; --i) { for (long long l = 2; l <= n / i;) { long long q = n / (i * l), r = n / (i * q) + 1; large[i] -= (i * l <= b ? large[i * l] : small[n / (i * l)]) * (r - l); l = r; } } return {small, large}; } #line 7 "test/yosupo/sum_of_totient_function.test.cpp" using namespace std; using mint = Modint<998244353>; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); long long N; cin >> N; auto [small, large] = totient_summatory_table<mint>(N); mint ans = large[1]; cout << ans << endl; }