Submission #7659496


Source Code Expand

Copy
#include <cstdint>

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

using mint = modint<998244353>;

#include <vector>

void f(std::vector<mint> &a) {
  int n = a.size();
  for (int k = 1; k < n; ++k) {
    for (int i = k * 2; i < n; i += k) {
      a[k] += a[i];
    }
  }
}

void inv_f(std::vector<mint> &a) {
  int n = a.size();
  for (int k = n - 1; k >= 1; --k) {
    for (int i = k * 2; i < n; i += k) {
      a[k] -= a[i];
    }
  }
}

#include <iostream>

int main() {
  constexpr int Max = 1000000;
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (int &e : a) {
    std::cin >> e;
  }

  std::vector<mint> x(Max + 1);
  for (const int e : a) {
    x[e] += mint(e);
  }

  f(x);

  std::vector<mint> y(Max + 1);
  for (int i = 1; i <= Max; ++i) {
    y[i] = x[i] * x[i];
  }

  inv_f(y);

  // i=j を除去
  for (const int e : a) {
    y[e] -= mint(e) * mint(e);
  }
  // i>j を除去
  for (int i = 1; i <= Max; ++i) {
    y[i] /= mint(2);
  }

  mint ans = 0;
  for (int i = 1; i <= Max; ++i) {
    ans += y[i] / mint(i);
  }

  std::cout << ans.value() << std::endl;

  return 0;
}

Submission Info

Submission Time
Task C - LCMs
User noshi91
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2479 Byte
Status AC
Exec Time 420 ms
Memory 16640 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 21
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 342 ms 15872 KB
01-02.txt AC 377 ms 16384 KB
01-03.txt AC 394 ms 16512 KB
01-04.txt AC 353 ms 15872 KB
01-05.txt AC 387 ms 16384 KB
01-06.txt AC 380 ms 16256 KB
01-07.txt AC 367 ms 16128 KB
01-08.txt AC 385 ms 16384 KB
01-09.txt AC 362 ms 16128 KB
01-10.txt AC 405 ms 16640 KB
01-11.txt AC 405 ms 16640 KB
01-12.txt AC 404 ms 16640 KB
01-13.txt AC 406 ms 16640 KB
01-14.txt AC 415 ms 16640 KB
01-15.txt AC 415 ms 16640 KB
01-16.txt AC 414 ms 16640 KB
01-17.txt AC 415 ms 16640 KB
01-18.txt AC 420 ms 16640 KB
sample-01.txt AC 342 ms 16000 KB
sample-02.txt AC 352 ms 15872 KB
sample-03.txt AC 352 ms 15872 KB