結果
問題 | 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 functemplate <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-2k += n - 1;dat[k] = a;while (k > 0) {// k -> parent nodek = (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;}