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 |
|
|
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 |