結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:25:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,142 ms / 2,000 ms |
コード長 | 13,591 bytes |
コンパイル時間 | 2,098 ms |
コンパイル使用メモリ | 138,188 KB |
実行使用メモリ | 83,328 KB |
最終ジャッジ日時 | 2024-09-16 13:21:26 |
合計ジャッジ時間 | 23,632 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS#pragma GCC target("avx")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <algorithm>#include <bitset>#include <cassert>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <ctime>#include <deque>#include <fstream>#include <functional>#include <iomanip>#include <iostream>#include <iterator>#include <list>#include <map>#include <memory>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#define rep(i, n) for(int i=0;i<(int)(n);i++)#define REP(i, n) for(int i=1;i<=(int)(n);i++)#define all(V) V.begin(),V.end()typedef long long lint;typedef std::pair<lint, lint> P;constexpr int INF = INT_MAX / 10;constexpr lint LINF = LLONG_MAX / 10;constexpr double eps = 1e-9;template<class T>class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};template<class T, class Alloc = std::allocator<T>>class Vector {using traits = std::allocator_traits<Alloc>;public:using value_type = T;using allocator_type = Alloc;using size_type = unsigned int;using difference_type = int;using reference = T&;using const_reference = const T&;using pointer = typename traits::pointer;using const_pointer = typename traits::const_pointer;class iterator {public:using difference_type = int;using value_type = Vector::value_type;using pointer = Vector::pointer;using reference = Vector::reference;using iterator_category = std::random_access_iterator_tag;private:pointer p;public:iterator()noexcept :p() {}iterator(const Vector& base, difference_type index) noexcept :p(base.e + index) {}iterator(const iterator& i) :p(i.p) {}iterator& operator=(const iterator& i) = default;iterator& operator=(iterator&& i)noexcept = default;iterator& operator++() {p++;return *this;}iterator operator++(int) {iterator res = *this;p++;return res;}iterator operator+(const difference_type& x)const {iterator res = *this;return res += x;}iterator& operator+=(const difference_type& x) {p += x;return *this;}iterator& operator--() {p--;return *this;}iterator operator--(int) {iterator res = *this;p--;return res;}iterator operator-(const difference_type x)const {iterator res = *this;return res -= x;}difference_type operator-(const iterator& i)const {return p - i.p;}iterator& operator-=(const difference_type x) {p -= x;return *this;}reference operator*()const {return *p;}reference operator[](const difference_type x)const {return *(p + x);}bool operator<(const iterator& i)const {return p < i.p;}bool operator<=(const iterator& i)const {return p <= i.p;}bool operator==(const iterator& i)const {return p == i.p;}bool operator>(const iterator& i)const {return p > i.p;}bool operator>=(const iterator& i)const {return p >= i.p;}bool operator!=(const iterator& i)const {return p != i.p;}};class const_iterator {public:using difference_type = int;using value_type = Vector::value_type;using pointer = const Vector::pointer;using reference = const Vector::reference;using iterator_category = std::random_access_iterator_tag;private:pointer p;public:const_iterator()noexcept :p() {}const_iterator(const Vector& base, difference_type index) noexcept :p(base.e + index) {}const_iterator(const const_iterator& i) :p(i.p) {}const_iterator& operator=(const const_iterator& i)noexcept = default;const_iterator& operator=(const_iterator&& i)noexcept = default;const_iterator& operator++() {p++;return *this;}const_iterator operator++(int) {const_iterator res = *this;p++;return res;}const_iterator operator+(const difference_type x)const {const_iterator res = *this;return res += x;}const_iterator& operator+=(const difference_type x) {p += x;return *this;}const_iterator& operator--() {p--;return *this;}const_iterator operator--(int) {const_iterator res = *this;p--;return res;}const_iterator operator-(const difference_type x)const {const_iterator res = *this;return res -= x;}difference_type operator-(const const_iterator& i)const {return p - i.p;}const_iterator& operator-=(const difference_type x) {p -= x;return *this;}reference operator*()const {return *p;}reference operator[](const difference_type x)const {return *(p + x);}bool operator<(const const_iterator& i)const {return p < i.p;}bool operator<=(const const_iterator& i)const {return p <= i.p;}bool operator==(const const_iterator& i)const {return p == i.p;}bool operator>(const const_iterator& i)const {return p > i.p;}bool operator>=(const const_iterator& i)const {return p >= i.p;}bool operator!=(const const_iterator& i)const {return p != i.p;}};using reverse_iterator = std::reverse_iterator<iterator>;using const_reverse_iterator = std::reverse_iterator<const_iterator>;private:pointer e;size_type length = 0, cap = 1;Alloc alloc;static_assert(std::is_same<T, typename Alloc::value_type>::value, "The allocator value type is not matched the Vector value type.");static_assert(!std::is_const<T>::value, "This library forbids containers of const elements");public:Vector() :Vector(Alloc()) {}explicit Vector(const Alloc& a)noexcept :alloc(a) {e = alloc.allocate(cap);}explicit Vector(size_type n, const Alloc& a = Alloc()) :alloc(a) {while (cap < n)cap *= 2;e = alloc.allocate(cap);rep(i, n)emplace_back();}explicit Vector(size_type n, const_reference value, const Alloc& a = Alloc()) :alloc(a) {while (cap < n)cap *= 2;e = alloc.allocate(cap);rep(i, n)emplace_back(value);}template<class InputIter>Vector(InputIter first, InputIter last, const Alloc& a = Alloc()) :alloc(a) {e = alloc.allocate(cap);for (InputIter i = first; i != last; i++) {emplace_back(*i);}}Vector(const Vector& x, const Alloc& a = Alloc()) :alloc(a) {while (cap < x.length)cap *= 2;length = x.length;e = alloc.allocate(cap);rep(i, x.length)traits::construct(alloc, e + i, *(x.e + i));}Vector(Vector&& x, const Alloc& a = Alloc()) :alloc(a) {cap = x.cap;length = x.length;e = x.e;x.e = nullptr;}~Vector() {if (e != nullptr) {rep(i, length)traits::destroy(alloc, e + i);alloc.deallocate(e, cap);}}Vector& operator=(const Vector& x) {rep(i, length)traits::destroy(alloc, e + i);alloc.deallocate(e, cap);length = x.length;cap = 1;while (cap < length)cap *= 2;e = alloc.allocate(cap);rep(i, length)traits::construct(alloc, e + i, *(x.e + i));return *this;}Vector& operator=(Vector&& x) {rep(i, length)traits::destroy(alloc, e + i);alloc.deallocate(e, cap);cap = x.cap;length = x.length;e = x.e;x.e = nullptr;return *this;}private:void extension() {pointer e_ = alloc.allocate(cap * 2);rep(i, length)traits::construct(alloc, e_ + i, *(e + i));rep(i, length)traits::destroy(alloc, e + i);alloc.deallocate(e, cap);e = e_;cap *= 2;}void extension(size_type n) {unsigned int r = 1;while (cap * r < n)r *= 2;if (r == 1)return;pointer e_ = alloc.allocate(cap * r);rep(i, length)traits::construct(alloc, e_ + i, *(e + i));rep(i, length)traits::destroy(alloc, e + i);alloc.deallocate(e, cap);e = e_;cap *= r;}public:template<class InputIter>void assign(InputIter first, InputIter last) {size_type cnt = 0;for (InputIter i = first; i != last; i++) {if (cnt == cap) {length = std::max(length, cnt);extension();}traits::construct(alloc, e + cnt, *i);cnt++;}}void assign(size_type n, const_reference value) {extension(n);std::fill(e, e + n, value);}template<class... Args>void emplace_back(Args&&... args) {if (length == cap)extension();traits::construct(alloc, e + length, std::forward<Args>(args)...);length++;}void push_back(const_reference value) {emplace_back(value);}void push_back(T&& value) {emplace_back(std::move(value));}void pop_back() {traits::destroy(alloc, e + length);length--;}void reserve(size_type n) {extension(n);}iterator erase(iterator pos) {const iterator res = pos;iterator t = pos; t++;for (iterator i = pos; t != end(); i++, t++) {*i = std::move(*t);}pop_back();return res;}iterator erase(iterator first, iterator last) {const iterator res = first;typename iterator::difference_type d = last - first;for (iterator i = first; i + d != end(); i++) {*i = std::move(*(i + d));}rep(i, d)pop_back();return res;}void swap(Vector& x) {std::swap(length, x.length);std::swap(cap, x.cap);std::swap(e, x.e);}void clear() {while (length)pop_back();}size_type size()const {return length;}void resize(size_type n, const_reference value = T()) {extension(n);while (n < length)pop_back();length = n;std::fill(e, e + n, value);}size_type capacity()const {return cap;}bool empty()const {return !length;}reference operator[](const size_type pos) {return e[pos];}pointer data() {return e;}reference front() {return *e;}reference back() {return *(e + length - 1);}iterator begin() noexcept {return iterator(*this, 0);}const_iterator begin()const noexcept {return const_iterator(*this, 0);}const_iterator cbegin()const noexcept {return const_iterator(*this, 0);}iterator rbegin()noexcept {return reverse_iterator(*this, 0);}const_iterator rbegin()const noexcept {return const_reverse_iterator(*this, 0);}const_iterator crbegin()const noexcept {return const_reverse_iterator(*this, 0);}iterator end() noexcept {return iterator(*this, length);}const_iterator end()const noexcept {return const_iterator(*this, length);}const_iterator cend()const noexcept {return const_iterator(*this, length);}iterator rend()noexcept {return reverse_iterator(*this, length);}const_iterator rend()const noexcept {return const_reverse_iterator(*this, length);}const_iterator crend()const noexcept {return const_reverse_iterator(*this, length);}};template <class T, class U>inline bool chmax(T& lhs, const U& rhs) {if (lhs < rhs) {lhs = rhs;return 1;}return 0;}template <class T, class U>inline bool chmin(T& lhs, const U& rhs) {if (lhs > rhs) {lhs = rhs;return 1;}return 0;}inline lint gcd(lint a, lint b) {while (b) {lint c = a;a = b; b = c % b;}return a;}inline lint lcm(lint a, lint b) {return a / gcd(a, b) * b;}bool isprime(lint n) {if (n == 1)return false;for (int i = 2; i * i <= n; i++) {if (n % i == 0)return false;}return true;}lint mypow(lint a, lint b) {if (!b)return 1;if (b & 1)return mypow(a, b - 1) * a;lint memo = mypow(a, b >> 1);return memo * memo;}lint modpow(lint a, lint b, lint m) {if (!b)return 1;if (b & 1)return modpow(a, b - 1, m) * a % m;lint memo = modpow(a, b >> 1, m);return memo * memo % m;}template<typename T>void printArray(std::vector<T>& vec) {rep(i, vec.size() - 1)std::cout << vec[i] << " ";std::cout << vec.back() << std::endl;}template<typename T>void printArray(Vector<T>& vec) {rep(i, vec.size() - 1)std::cout << vec[i] << " ";std::cout << vec.back() << std::endl;}template<typename T>void printArray(T l, T r) {T rprev = r;rprev--;for (T i = l; i != rprev; i++) {std::cout << *i << " ";}std::cout << *rprev << std::endl;}std::string to_string(Vector<int>& vec) {std::string res = "[";rep(i, vec.size() - 1)res += std::to_string(vec[i]) + ", ";res += std::to_string(vec.back()) + "]";return res;}template<typename T>class SparseTable {T** table;int* logtable;bool ismax;public:SparseTable(Vector<T> vec, bool ismax = false) :ismax(ismax) {int maxlength = 0;while ((1 << (maxlength + 1)) <= vec.size())maxlength++;table = new T * [maxlength + 1];logtable = new int[vec.size() + 1];rep(i, maxlength + 1) {table[i] = new T[vec.size()];rep(j, vec.size() - (1 << i) + 1) {if (i) {if (!ismax)table[i][j] = gcd(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);else table[i][j] = gcd(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);}else table[i][j] = vec[j];}}logtable[1] = 0;for (int i = 2; i <= vec.size(); i++) {logtable[i] = logtable[i >> 1] + 1;}}T query(int l, int r) {int length = r - l;if (!ismax)return gcd(table[logtable[length]][l], table[logtable[length]][r - (1 << logtable[length])]);else return gcd(table[logtable[length]][l], table[logtable[length]][r - (1 << logtable[length])]);}};lint n;Vector<lint> a;int main() {std::cin >> n;a.resize(n);rep(i, n)std::cin >> a[i];SparseTable<lint> st(a);lint ans = 0, l = 0, r = 0, now = -1;while (r != n) {if (now == -1)now = a[r];else now = gcd(now, a[r]);r++;while (now == 1) {l++;ans += r - l;if (l == r)now = -1;else now = st.query(l, r);}}ans += (r - l) * (r - l + 1) / 2;std::cout << n * (n + 1) / 2 - ans << std::endl;return 0;}