結果
問題 | No.1036 Make One With GCD 2 |
ユーザー | kimiyuki |
提出日時 | 2020-04-24 22:14:34 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 879 ms / 2,000 ms |
コード長 | 3,279 bytes |
コンパイル時間 | 849 ms |
コンパイル使用メモリ | 62,024 KB |
実行使用メモリ | 84,800 KB |
最終ジャッジ日時 | 2023-10-14 19:21:07 |
合計ジャッジ時間 | 15,305 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 247 ms
84,760 KB |
testcase_01 | AC | 215 ms
84,712 KB |
testcase_02 | AC | 231 ms
84,680 KB |
testcase_03 | AC | 68 ms
31,360 KB |
testcase_04 | AC | 118 ms
55,776 KB |
testcase_05 | AC | 1 ms
4,372 KB |
testcase_06 | AC | 2 ms
4,368 KB |
testcase_07 | AC | 89 ms
35,896 KB |
testcase_08 | AC | 75 ms
29,780 KB |
testcase_09 | AC | 341 ms
82,748 KB |
testcase_10 | AC | 316 ms
77,016 KB |
testcase_11 | AC | 354 ms
84,444 KB |
testcase_12 | AC | 330 ms
77,876 KB |
testcase_13 | AC | 483 ms
80,628 KB |
testcase_14 | AC | 497 ms
81,680 KB |
testcase_15 | AC | 465 ms
76,580 KB |
testcase_16 | AC | 471 ms
77,260 KB |
testcase_17 | AC | 494 ms
79,660 KB |
testcase_18 | AC | 2 ms
4,372 KB |
testcase_19 | AC | 3 ms
4,368 KB |
testcase_20 | AC | 3 ms
4,372 KB |
testcase_21 | AC | 2 ms
4,368 KB |
testcase_22 | AC | 465 ms
75,740 KB |
testcase_23 | AC | 331 ms
56,380 KB |
testcase_24 | AC | 472 ms
78,928 KB |
testcase_25 | AC | 435 ms
71,916 KB |
testcase_26 | AC | 445 ms
74,392 KB |
testcase_27 | AC | 1 ms
4,372 KB |
testcase_28 | AC | 1 ms
4,368 KB |
testcase_29 | AC | 1 ms
4,372 KB |
testcase_30 | AC | 1 ms
4,372 KB |
testcase_31 | AC | 2 ms
4,372 KB |
testcase_32 | AC | 1 ms
4,368 KB |
testcase_33 | AC | 2 ms
4,368 KB |
testcase_34 | AC | 1 ms
4,372 KB |
testcase_35 | AC | 1 ms
4,368 KB |
testcase_36 | AC | 1 ms
4,372 KB |
testcase_37 | AC | 2 ms
4,372 KB |
testcase_38 | AC | 227 ms
84,716 KB |
testcase_39 | AC | 268 ms
84,704 KB |
testcase_40 | AC | 340 ms
56,356 KB |
testcase_41 | AC | 879 ms
84,760 KB |
testcase_42 | AC | 857 ms
84,760 KB |
testcase_43 | AC | 712 ms
84,800 KB |
testcase_44 | AC | 819 ms
84,760 KB |
ソースコード
#line 1 "main.cpp" #define PROBLEM "https://yukicoder.me/problems/no/1036" #include <cstdio> #include <vector> #line 2 "/home/user/GitHub/competitive-programming-library/utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 2 "/home/user/GitHub/competitive-programming-library/data_structure/sparse_table.hpp" #include <cassert> #line 5 "/home/user/GitHub/competitive-programming-library/data_structure/sparse_table.hpp" /** * @brief Sparse Table (idempotent monoid) * @note the unit is required just for convenience * @note $O(N \log N)$ space */ template <class IdempotentMonoid> struct sparse_table { typedef typename IdempotentMonoid::value_type value_type; std::vector<std::vector<value_type> > table; IdempotentMonoid mon; sparse_table() = default; /** * @note $O(N \log N)$ time */ template <class InputIterator> sparse_table(InputIterator first, InputIterator last, const IdempotentMonoid & mon_ = IdempotentMonoid()) : mon(mon_) { table.emplace_back(first, last); int n = table[0].size(); int log_n = 32 - __builtin_clz(n); table.resize(log_n, std::vector<value_type>(n)); REP (k, log_n - 1) { REP (i, n) { table[k + 1][i] = i + (1ll << k) < n ? mon.mult(table[k][i], table[k][i + (1ll << k)]) : table[k][i]; } } } /** * @note $O(1)$ */ value_type range_get(int l, int r) const { if (l == r) return mon.unit(); // if there is no unit, remove this line assert (0 <= l and l < r and r <= (int)table[0].size()); int k = 31 - __builtin_clz(r - l); // log2 return mon.mult(table[k][l], table[k][r - (1ll << k)]); } }; #line 2 "/home/user/GitHub/competitive-programming-library/number/gcd.hpp" #include <algorithm> /** * @note if arguments are negative, the result may be negative */ template <typename T> T gcd(T a, T b) { while (a) { b %= a; std::swap(a, b); } return b; } template <typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; } #line 3 "/home/user/GitHub/competitive-programming-library/monoids/gcd.hpp" /** * @note a semilattice */ template <class Integer> struct gcd_monoid { typedef Integer value_type; Integer unit() const { return 0; } Integer mult(Integer a, Integer b) const { return gcd(a, b); } }; #line 7 "main.cpp" long long solve(int n, const std::vector<long long> & a) { sparse_table<gcd_monoid<long long> > table(ALL(a)); int r = 0; long long ans = 0; REP (l, n) { while (r < n and table.range_get(l, r) != 1) { ++ r; } if (r == n and table.range_get(l, r) != 1) { break; } ans += n - r + 1; } return ans; } int main() { int n; scanf("%d", &n); std::vector<long long> a(n); REP (i, n) { scanf("%lld", &a[i]); } printf("%lld\n", solve(n, a)); return 0; }