結果
問題 | No.2046 Ans Mod? Mod Ans! |
ユーザー |
![]() |
提出日時 | 2022-08-09 21:19:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 4,000 ms |
コード長 | 1,815 bytes |
コンパイル時間 | 1,878 ms |
コンパイル使用メモリ | 109,768 KB |
実行使用メモリ | 5,632 KB |
最終ジャッジ日時 | 2024-12-16 08:13:40 |
合計ジャッジ時間 | 2,449 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#pragma GCC optimize("O3,unroll-loops") #include <algorithm> #include <bitset> #include <iostream> #include <numeric> #include <utility> #include <vector> using namespace std; using lint = long long; #include <cstdio> #include <string> template <typename T> T rd_integer() { T ret = 0; bool minus = false; char c = getchar_unlocked(); while (!isdigit(c)) minus |= (c == '-'), c = getchar_unlocked(); while (isdigit(c)) ret = (ret << 1) + (ret << 3) + (c ^ 48), c = getchar_unlocked(); return minus ? -ret : ret; } int rdi() { return rd_integer<int>(); } // f[n] に対して、全ての n の倍数 n*i に対する f[n*i] の和が出てくる 計算量 O(N loglog N) // 素数p毎に処理する高速ゼータ変換 // 使用例 https://yukicoder.me/submissions/385043 template <class T> void multiple_zeta(std::vector<T> &f) { int N = int(f.size()) - 1; std::vector<int> is_prime(N + 1, 1); for (int p = 2; p <= N; p++) { if (is_prime[p]) { for (int q = p * 2; q <= N; q += p) is_prime[q] = 0; for (int j = N / p; j > 0; --j) f[j] += f[j * p]; } } } constexpr int sz = 200002; int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N = rdi(); bitset<sz> contains; vector<lint> cumsum(sz); lint sumupper = 0; for (int i = 0; i < N; ++i) { int a = rdi(); contains.set(a); cumsum[a] = 1; sumupper += a; } for (int a = 1; a < sz; ++a) cumsum[sz - a - 1] += cumsum[sz - a]; multiple_zeta(cumsum); int numhi = N; lint ret = 0; for (int a = 1; a < sz; ++a) { if (contains[a]) { --numhi; sumupper -= a; ret += (numhi - 1 + cumsum[a]) * a - sumupper; } } cout << ret << '\n'; }