結果
問題 | No.1233 割り切れない気持ち |
ユーザー |
|
提出日時 | 2020-09-18 22:29:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 66 ms / 3,153 ms |
コード長 | 3,428 bytes |
コンパイル時間 | 2,151 ms |
コンパイル使用メモリ | 198,204 KB |
最終ジャッジ日時 | 2025-01-14 17:33:05 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
ソースコード
#include <bits/stdc++.h> #ifdef DEBUG #include <Mylib/Debug/debug.cpp> #else #define dump(...) ((void)0) #endif template <typename T, typename U> bool chmin(T &a, const U &b){ return (a > b ? a = b, true : false); } template <typename T, typename U> bool chmax(T &a, const U &b){ return (a < b ? a = b, true : false); } template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){ std::fill((U*)a, (U*)(a + N), v); } template <typename T, size_t N, size_t I = N> auto make_vector(const std::array<int, N> &a, T value = T()){ static_assert(I >= 1); static_assert(N >= 1); if constexpr (I == 1){ return std::vector<T>(a[N - I], value); }else{ return std::vector(a[N - I], make_vector<T, N, I - 1>(a, value)); } } template <typename T> std::ostream& operator<<(std::ostream &s, const std::vector<T> &a){ for(auto it = a.begin(); it != a.end(); ++it){ if(it != a.begin()) s << " "; s << *it; } return s; } template <typename T> std::istream& operator>>(std::istream &s, std::vector<T> &a){ for(auto &x : a) s >> x; return s; } namespace haar_lib { template <typename T, typename Add = std::plus<T>, typename Minus = std::minus<T>> class cumulative_sum_1d { std::vector<T> data; const int N; const Add add; const Minus minus; bool is_built = false; public: cumulative_sum_1d(const std::vector<T> &a, const T &e = 0, const Add &add = Add(), const Minus &minus = Minus()): N(a.size()), add(add), minus(minus) { data.assign(N + 1, e); for(int i = 0; i < N; ++i) data[i + 1] = a[i]; } cumulative_sum_1d(int N, const T &e = 0, const Add &add = Add(), const Minus &minus = Minus()): N(N), add(add), minus(minus) { data.assign(N + 1, e); } auto& update(int i, const T &val){ assert(not is_built); data[i + 1] = add(data[i + 1], val); return *this; } auto& build(){ assert(not is_built); for(int i = 0; i < N; ++i) data[i + 1] = add(data[i + 1], data[i]); is_built = true; return *this; } /** * @attention [i, j) */ T get(int i, int j) const { assert(is_built); return minus(data[j], data[i]); } }; } namespace haar_lib {} namespace solver { using namespace haar_lib; constexpr int m1000000007 = 1000000007; constexpr int m998244353 = 998244353; void init(){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(12); std::cerr << std::fixed << std::setprecision(12); std::cin.exceptions(std::ios_base::failbit); } constexpr int MAX = 200000; void solve(){ int N; std::cin >> N; std::vector<int64_t> A(N); std::cin >> A; std::vector<int> count(MAX + 1); for(auto x : A) count[x] += 1; cumulative_sum_1d cs(count); cs.build(); int64_t sum = std::accumulate(A.begin(), A.end(), 0LL); int64_t ans = 0; dump(cs.get(1, MAX + 1)); for(int i = 1; i <= MAX; ++i){ if(count[i] == 0) continue; ans += sum * count[i]; dump(ans); for(int j = i; j <= MAX; j += i){ ans -= (int64_t)i * cs.get(j, MAX + 1) * count[i]; } dump(ans); } std::cout << ans << "\n"; } } int main(){ solver::init(); while(true){ try{ solver::solve(); }catch(const std::istream::failure &e){ break; } } return 0; }