Submission #31096016

---

Source Code Expand

#include <vector>
#include <numeric>
#include <set>
using i64 = long long;


struct osa_k {
  using int_type = int;
  std::vector<int_type> min_fact;

  // O(NlogN)
  static std::vector<int_type> min_prime_factor(int n) {
    std::vector<int_type> res(n);
    std::iota(std::begin(res), std::end(res), 0);
    for(int i = 2; i * i < n; i++) {
      if(res[i] < i) continue;
      for(int j = i * i; j < n; j += i) {
        if(res[j] == j) res[j] = i;
      }
    }
    return res;
  }

  void build(int n) {
    min_fact = min_prime_factor(n);
  }

  // O(logN)
  std::vector<std::pair<int_type, int>> prime_factors(int n) const {
    std::vector<std::pair<int_type, int>> res;
    while(n > 1) {
      if(res.empty() || res.back().first != min_fact[n]) {
        res.push_back({ min_fact[n], 0 });
      }
      res.back().second++;
      n /= min_fact[n];
    }
    return res;
  }
  
  // The divisors are not sorted
  // O(logN + |divisors|)
  template<class F>
  void enumerate_divisors(int n, F f) const {
    std::vector<std::pair<int_type, int>> prime_facts = prime_factors(n);
    if(prime_facts.empty()) {
      f(1);
      return;
    }
    std::vector<int> cnt(prime_facts.size());
    std::vector<int> acc(prime_facts.size(), 1);
    while(true){
      f(acc.front());
      int i = 0;
      for(; i < prime_facts.size(); i++) {
        if((cnt[i]++) == prime_facts[i].second) {
          cnt[i] = 0;
        }
        else {
          acc[i] *= prime_facts[i].first;
          break;
        }
      }
      if(i == prime_facts.size()) {
        break;
      }
      while(i --> 0) {
        acc[i] = acc[i + 1];
      }
    }
  }
};

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define STRINGIFY(n) #n
#define TOSTRING(n) STRINGIFY(n)
#define PREFIX "#" TOSTRING(__LINE__) "| "
#define debug(x) \
{ \
  std::cout << PREFIX << #x << " = " << x << std::endl; \
}
std::ostream& output_indent(std::ostream& os, int ind) {
  for(int i = 0; i < ind; i++) os << " ";
  return os;
}
template<class S, class T> std::ostream& operator<<(std::ostream& os, const std::pair<S, T>& p);
template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<class S, class T> std::ostream& operator<<(std::ostream& os, const std::pair<S, T>& p) {
  return (os << "(" << p.first << ", " << p.second << ")");
}
template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << "[";
  for(int i = 0;i < v.size();i++) os << v[i] << ", ";
  return (os << "]");
}
template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) { return std::vector<T>(n, std::forward<T>(val)); }
template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

 
template<uint32_t M>
struct montgomery_modint {
  using Self = montgomery_modint<M>;
  using i32 = int32_t;
  using u32 = uint32_t;
  using u64 = uint64_t;
 
  static constexpr u32 get_r() {
    u32 res = M;
    for(int i = 0; i < 4; i++) res *= 2 - M * res;
    return res;
  }
  static constexpr u32 reduce(u64 a) {
    return (a + u64(u32(a) * u32(-r)) * M) >> 32;
  }
 
  static constexpr u32 r = get_r();
  static constexpr u32 n2 = -u64(M) % M;
 
  u32 a;
 
  constexpr montgomery_modint() : a(0) {}
  constexpr montgomery_modint(int64_t a) : a(reduce(u64(a % M + M) * n2)) {}
 
  constexpr u32 val() const {
    u32 res = reduce(a);
    return res >= M ? res - M : res;
  }
  constexpr Self pow(u64 r) const {
    Self ans(1); Self aa = *this;
    while(r) { if(r & 1) ans *= aa; aa *= aa; r >>= 1; }
    return ans;
  }
  constexpr Self inv() const { return this->pow(M - 2); }
  constexpr Self& operator+=(const Self& r) {
    if(i32(a += r.a - 2 * M) < 0) a += 2 * M;
    return *this;
  }
  constexpr Self& operator-=(const Self& r) {
    if(i32(a -= r.a) < 0) a += 2 * M;
    return *this;
  }
  constexpr Self& operator*=(const Self& r) {
    a = reduce(u64(a) * r.a);
    return *this;
  }
  constexpr Self& operator/=(const Self& r) {
    *this *= r.inv();
    return *this;
  }
  constexpr Self operator+(const Self r) const { return Self(*this) += r; }
  constexpr Self operator-(const Self r) const { return Self(*this) -= r; }
  constexpr Self operator-() const { return Self() - Self(*this); }
  constexpr Self operator*(const Self r) const { return Self(*this) *= r; }
  constexpr Self operator/(const Self r) const { return Self(*this) /= r; }
  constexpr bool operator==(const Self& r) const {
    return (a >= M ? a - M : a) == (r.a >= M ? r.a - M : r.a);
  }
  constexpr bool operator!=(const Self& r) const {
    return (a >= M ? a - M : a) == (r.a >= M ? r.a - M : r.a);
  }
};
 
template<uint32_t M>
std::ostream& operator<<(std::ostream& os, const montgomery_modint<M>& m) {
  return os << m.val();
}
template<uint32_t M>
std::istream& operator>>(std::istream& is, montgomery_modint<M>& m) {
  int64_t t;
  is >> t;
  m = montgomery_modint<M>(t);
  return is;
}
 
template<uint32_t mod>
using modint = montgomery_modint<mod>;
 
 
 
using fp = modint<998244353>;
 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
 
template <class T>
void divisor_transform(vector<T> &a) {
    int n = a.size();
    vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (sieve[p]) {
            for (int k = 1; k * p < n; ++k) {
                sieve[k * p] = false;
                a[k * p] += a[k];
            }
        }
    }
    for (int i = 0; ++i != n;) {
        a[i] += a[0];
    }
}
 
template <class T>
void inverse_divisor_transform(vector<T> &a) {
    int n = a.size();
    vector<bool> sieve(n, true);
    for (int i = 0; ++i != n;) {
        a[i] -= a[0];
    }
    for (int p = 2; p < n; ++p) {
        if (sieve[p]) {
            for (int k = (n - 1) / p; k != 0; --k) {
                sieve[k * p] = false;
                a[k * p] -= a[k];
            }
        }
    }
 
}
 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
 
template <class T>
void multiple_transform(vector<T> &a) {
    int n = a.size();
    vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (sieve[p]) {
            for (int k = (n - 1) / p; k != 0; --k) {
                sieve[k * p] = false;
                a[k] += a[k * p];
            }
        }
    }
    for (int i = 0; ++i != n;) {
        a[i] += a[0];
    }
}
 
template <class T>
void inverse_multiple_transform(vector<T> &a) {
    int n = a.size();
    vector<bool> sieve(n, true);
    for (int i = 0; ++i != n;) {
        a[i] -= a[0];
    }
    for (int p = 2; p < n; ++p) {
        if (sieve[p]) {
            for (int k = 1; k * p < n; ++k) {
                sieve[k * p] = false;
                a[k] -= a[k * p];
            }
        }
    }
}
 
constexpr i64 MAX = 1e6 + 1;
 
int main() {
  i64 N;
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  cin >> N;
  vector<i64> A(N);
  rep(i,0,N) cin >> A[i];

  osa_k osa;
  osa.build(MAX);
  vector<fp> S(MAX);
 
  vector<fp> ans(MAX);
 
  rep(i,0,N) {
    osa.enumerate_divisors(A[i], [&](int d) {
        S[d] += fp(A[i]);
        ans[d] -= fp(A[i]) * fp(A[i]);
    });
  }
  fp i2 = fp(2).inv();
  rep(g,1,MAX) {
    ans[g] += S[g] * S[g];
    ans[g] *= i2;
  }
 
  inverse_multiple_transform(ans);
 
  fp res;
  rep(g,1,MAX) {
    res += fp(g).inv() * ans[g];
  }
  cout << res << endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:77:28: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   77 | #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
      |                            ^
./Main.cpp:275:3: note: in expansion of macro ‘rep’
  275 |   rep(i,0,N) cin >> A[i];
      |   ^~~
./Main.cpp:77:28: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   77 | #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
      |                            ^
./Main.cpp:283:3: note: in expansion of macro ‘rep’
  283 |   rep(i,0,N) {
      |   ^~~
./Main.cpp:77:28: warning: unnecessary parentheses in declaration of ‘g’ [-Wparentheses]
   77 | #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
      |                            ^
./Main.cpp:290:3: note: in expansion of macro ‘rep’
  290 |   rep(g,1,MAX) {
      |   ^~~
./Main.cpp:77:28: warning: unnecessary parentheses in declaration of ‘g’ [-Wparentheses]
   77 | #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
      |                            ^
./Main.cpp:298:3: note: in expansion of macro ‘rep’
  298 |   rep(g,1,MAX) {
      |   ^~~
./Main.cpp: In instantiation of ‘void osa_k::enumerate_divisors(int, F) const [with F = main()::<lambda(int)>]’:
./Main.cpp:287:6:   required from here
./Main.cpp:55:15: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   55 |       for(; i < prime_facts.size(); i++) {
      |             ~~^~~~~~~~~~~~~~~~~~~~
./Main.cpp:64:12: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   64 |       if(i == prime_facts.size()) {
      |          ~~^~~~~~~~~~~~~~~~~~~~~

Judge Result