This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://atcoder.jp/contests/agc038/tasks/agc038_c" #include <iostream> #include <atcoder/modint> #include "library/convolution/gcd_convolution.hpp" using mint = atcoder::modint998244353; constexpr int M = 1000000; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<mint> count(M + 1, 0); for (int i = 0; i < n; ++i) { int v; std::cin >> v; ++count[v]; } std::vector<mint> f(M + 1); for (int i = 0; i <= M; ++i) f[i] = count[i] * i; auto c = suisen::gcd_convolution<mint>(f, f); mint ans = 0; for (int g = 1; g <= M; ++g) { ans += (c[g] - f[g] * f[g]) / (2 * g); } for (int i = 1; i <= M; ++i) { ans += count[i] * (count[i] - 1) * i / 2; } std::cout << ans.val() << std::endl; return 0; }
#line 1 "test/src/convolution/gcd_convolution/lcms.test.cpp" #define PROBLEM "https://atcoder.jp/contests/agc038/tasks/agc038_c" #include <iostream> #include <atcoder/modint> #line 1 "library/convolution/gcd_convolution.hpp" #line 1 "library/transform/multiple.hpp" #include <vector> #line 1 "library/util/default_operator.hpp" namespace suisen { namespace default_operator { template <typename T> auto zero() -> decltype(T { 0 }) { return T { 0 }; } template <typename T> auto one() -> decltype(T { 1 }) { return T { 1 }; } template <typename T> auto add(const T &x, const T &y) -> decltype(x + y) { return x + y; } template <typename T> auto sub(const T &x, const T &y) -> decltype(x - y) { return x - y; } template <typename T> auto mul(const T &x, const T &y) -> decltype(x * y) { return x * y; } template <typename T> auto div(const T &x, const T &y) -> decltype(x / y) { return x / y; } template <typename T> auto mod(const T &x, const T &y) -> decltype(x % y) { return x % y; } template <typename T> auto neg(const T &x) -> decltype(-x) { return -x; } template <typename T> auto inv(const T &x) -> decltype(one<T>() / x) { return one<T>() / x; } } // default_operator namespace default_operator_noref { template <typename T> auto zero() -> decltype(T { 0 }) { return T { 0 }; } template <typename T> auto one() -> decltype(T { 1 }) { return T { 1 }; } template <typename T> auto add(T x, T y) -> decltype(x + y) { return x + y; } template <typename T> auto sub(T x, T y) -> decltype(x - y) { return x - y; } template <typename T> auto mul(T x, T y) -> decltype(x * y) { return x * y; } template <typename T> auto div(T x, T y) -> decltype(x / y) { return x / y; } template <typename T> auto mod(T x, T y) -> decltype(x % y) { return x % y; } template <typename T> auto neg(T x) -> decltype(-x) { return -x; } template <typename T> auto inv(T x) -> decltype(one<T>() / x) { return one<T>() / x; } } // default_operator } // namespace suisen #line 6 "library/transform/multiple.hpp" namespace suisen::multiple_transform { // Calculates `g` s.t. g(n) = Sum_{n | m} f(m) inplace. template <typename T, auto add = default_operator::add<T>> void zeta(std::vector<T> &f) { const int n = f.size(); std::vector<char> is_prime(n, true); auto cum = [&](const int p) { const int qmax = (n - 1) / p, rmax = qmax * p; for (int q = qmax, pq = rmax; q >= 1; --q, pq -= p) { f[q] = add(f[q], f[pq]); is_prime[pq] = false; } }; for (int p = 2; p < n; ++p) if (is_prime[p]) cum(p); } // Calculates `f` s.t. g(n) = Sum_{n | m} f(m) inplace. template <typename T, auto sub = default_operator::sub<T>> void mobius(std::vector<T> &f) { const int n = f.size(); std::vector<char> is_prime(n, true); auto diff = [&](const int p) { for (int q = 1, pq = p; pq < n; ++q, pq += p) { f[q] = sub(f[q], f[pq]); is_prime[pq] = false; } }; for (int p = 2; p < n; ++p) if (is_prime[p]) diff(p); } } // namespace suisen::multiple_transform #line 1 "library/convolution/convolution.hpp" #include <cassert> #line 6 "library/convolution/convolution.hpp" #line 8 "library/convolution/convolution.hpp" namespace suisen { namespace convolution { template <typename T, auto transform, auto inv_transform, auto mul = default_operator::mul<T>> std::vector<T> transform_convolution(std::vector<T> a, std::vector<T> b) { const std::size_t n = a.size(), m = b.size(); assert(n == m); transform(a), transform(b); for (std::size_t i = 0; i < n; ++i) a[i] = mul(a[i], b[i]); inv_transform(a); return a; } template <typename T, auto transform, auto inv_transform, auto mul = default_operator::mul<T>> std::vector<T> transform_convolution(std::vector<std::vector<T>> a) { const std::size_t num = a.size(); assert(num); const std::size_t n = a[0].size(); for (auto &v : a) { assert(n == int(v.size())); transform(v); } auto &res = a[0]; for (int i = 1; i < num; ++i) { for (int j = 0; j < n; ++j) res[j] = mul(res[j], a[i][j]); } inv_transform(res); return res; } } } // namespace suisen #line 6 "library/convolution/gcd_convolution.hpp" namespace suisen { template < typename T, auto add = default_operator::add<T>, auto sub = default_operator::sub<T>, auto mul = default_operator::mul<T> > auto gcd_convolution(std::vector<T> a, std::vector<T> b) { return convolution::transform_convolution< T, multiple_transform::zeta<T, add>, multiple_transform::mobius<T, sub>, mul >(std::move(a), std::move(b)); } } // namespace suisen #line 7 "test/src/convolution/gcd_convolution/lcms.test.cpp" using mint = atcoder::modint998244353; constexpr int M = 1000000; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<mint> count(M + 1, 0); for (int i = 0; i < n; ++i) { int v; std::cin >> v; ++count[v]; } std::vector<mint> f(M + 1); for (int i = 0; i <= M; ++i) f[i] = count[i] * i; auto c = suisen::gcd_convolution<mint>(f, f); mint ans = 0; for (int g = 1; g <= M; ++g) { ans += (c[g] - f[g] * f[g]) / (2 * g); } for (int i = 1; i <= M; ++i) { ans += count[i] * (count[i] - 1) * i / 2; } std::cout << ans.val() << std::endl; return 0; }