結果
問題 | 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)#endiftemplate <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;}