test/yosupo/number_theory/sum_of_totient_function.test.cpp

AC · 最終更新 2026-09-07 · GitHub

問題: https://judge.yosupo.jp/problem/sum_of_totient_function

依存するヘッダ（4）

internal/internal_math.hpp lib/internal/internal_math.hpp
internal/internal_type_traits.hpp lib/internal/internal_type_traits.hpp
modint (static_modint / dynamic_modint) lib/number_theory/modint.hpp
乗法的関数の累積和を劣線形で計算する（杜教筛 / Dirichlet 双曲線法） lib/number_theory/multiplicative_function.hpp

実装

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/sum_of_totient_function
#include <iostream>
#include "number_theory/modint.hpp"
#include "number_theory/multiplicative_function.hpp"

using Mint = modint998;

int main() {
    long long n;
    std::cin >> n;
    std::cout << totient_sum<Mint>(n) << '\n';
    return 0;
}