結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:19:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 828 ms / 2,000 ms |
コード長 | 2,955 bytes |
コンパイル時間 | 1,891 ms |
コンパイル使用メモリ | 172,620 KB |
実行使用メモリ | 19,200 KB |
最終ジャッジ日時 | 2024-09-16 13:20:11 |
合計ジャッジ時間 | 14,537 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#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; }