結果
問題 | No.1036 Make One With GCD 2 |
ユーザー | kibuna |
提出日時 | 2020-04-24 22:19:51 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 837 ms / 2,000 ms |
コード長 | 2,955 bytes |
コンパイル時間 | 4,803 ms |
コンパイル使用メモリ | 169,960 KB |
実行使用メモリ | 19,216 KB |
最終ジャッジ日時 | 2023-10-14 19:23:26 |
合計ジャッジ時間 | 15,810 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 408 ms
19,136 KB |
testcase_01 | AC | 97 ms
19,140 KB |
testcase_02 | AC | 257 ms
18,944 KB |
testcase_03 | AC | 21 ms
10,180 KB |
testcase_04 | AC | 34 ms
16,112 KB |
testcase_05 | AC | 1 ms
4,352 KB |
testcase_06 | AC | 2 ms
4,352 KB |
testcase_07 | AC | 39 ms
10,240 KB |
testcase_08 | AC | 33 ms
9,876 KB |
testcase_09 | AC | 263 ms
18,752 KB |
testcase_10 | AC | 246 ms
18,280 KB |
testcase_11 | AC | 268 ms
19,216 KB |
testcase_12 | AC | 248 ms
18,436 KB |
testcase_13 | AC | 449 ms
18,684 KB |
testcase_14 | AC | 453 ms
18,744 KB |
testcase_15 | AC | 426 ms
18,304 KB |
testcase_16 | AC | 429 ms
18,148 KB |
testcase_17 | AC | 443 ms
18,616 KB |
testcase_18 | AC | 2 ms
4,352 KB |
testcase_19 | AC | 2 ms
4,352 KB |
testcase_20 | AC | 3 ms
4,352 KB |
testcase_21 | AC | 2 ms
4,348 KB |
testcase_22 | AC | 420 ms
18,328 KB |
testcase_23 | AC | 314 ms
16,264 KB |
testcase_24 | AC | 437 ms
18,428 KB |
testcase_25 | AC | 400 ms
17,632 KB |
testcase_26 | AC | 415 ms
18,016 KB |
testcase_27 | AC | 2 ms
4,352 KB |
testcase_28 | AC | 2 ms
4,348 KB |
testcase_29 | AC | 1 ms
4,348 KB |
testcase_30 | AC | 2 ms
4,352 KB |
testcase_31 | AC | 2 ms
4,352 KB |
testcase_32 | AC | 2 ms
4,356 KB |
testcase_33 | AC | 2 ms
4,348 KB |
testcase_34 | AC | 2 ms
4,352 KB |
testcase_35 | AC | 2 ms
4,352 KB |
testcase_36 | AC | 2 ms
4,352 KB |
testcase_37 | AC | 1 ms
4,356 KB |
testcase_38 | AC | 255 ms
19,076 KB |
testcase_39 | AC | 837 ms
19,208 KB |
testcase_40 | AC | 313 ms
16,368 KB |
testcase_41 | AC | 542 ms
18,952 KB |
testcase_42 | AC | 540 ms
18,948 KB |
testcase_43 | AC | 495 ms
19,096 KB |
testcase_44 | AC | 533 ms
18,944 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using lint = long long; const lint inf = 1LL << 60; const lint mod = 1000000007; // greatest common divisor and least common multiple // gcd is calculated by Euclidean Algorithm // lcm = m * n / gcd(m,n) template <typename T = int> T gcd(T a, T b) { if (a < b) return gcd(b, a); if (b == 0) return a; T r; while ((r = a % b)) { a = b; b = r; } return b; } template <typename T = int> T lcm(T m, T n) { if ((0 == m) || (0 == n)) return 0; return ((m / gcd(m, n)) * n); } // 0-indexed bottom up Segment Tree // UNIT is the identity element of operation func template <typename T = int> struct SegmentTree { using F = function<T(T, T)>; int n; vector<T> dat; F func; T UNIT; SegmentTree(int n_, F func_, T UNIT_) : func(func_), UNIT(UNIT_) { n = 1; // full binary tree: num of leaves = n = 2^k >= n_ while (n < n_) n *= 2; dat.assign(2 * n - 1, UNIT); } SegmentTree(vector<T> v_, F func_, T UNIT_) : func(func_), UNIT(UNIT_) { n = 1; int nv = v_.size(); while (n < nv) n *= 2; dat.assign(2 * n - 1, UNIT); for (int i = 0; i < nv; ++i) { dat[n - 1 + i] = v_[i]; } for (int i = n - 2; i >= 0; --i) { dat[i] = func(dat[2 * i + 1], dat[2 * i + 2]); } } void update(int k, T a) { // leaves are at index n-1 to 2*n-2 k += n - 1; dat[k] = a; while (k > 0) { // k -> parent node k = (k - 1) / 2; // func(child nodes) dat[k] = func(dat[2 * k + 1], dat[2 * k + 2]); } } // get result of func() in [l, r) T query(int l, int r) { l += n - 1; r += n - 1; T retl = UNIT, retr = UNIT; while (l < r) { if ((l & 1) == 0) retl = func(retl, dat[l]); if ((r & 1) == 0) retr = func(dat[r - 1], retr); l = l / 2; r = (r - 1) / 2; } return func(retl, retr); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); lint n; cin >> n; vector<lint> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } lint unit = 0; auto f = [&](lint l, lint r) { if (l == 0) return r; else if (r == 0) return l; return gcd<lint>(l, r); }; SegmentTree<lint> seg(a, f, unit); int r = 1; lint g = a[0]; lint ret = 0; for (int i = 0; i < n; ++i) { if (r <= i) r = i + 1; g = seg.query(i, r); while (r < n && g != 1) { g = gcd(g, a[r]); r++; } if (g != 1) continue; ret += n - r + 1; } cout << ret << "\n"; return 0; }