結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2023-10-25 14:40:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 749 ms / 2,000 ms |
コード長 | 2,314 bytes |
コンパイル時間 | 1,368 ms |
コンパイル使用メモリ | 126,928 KB |
最終ジャッジ日時 | 2025-02-17 13:35:12 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<cstring>#include<cassert>#include<cmath>#include<ctime>#include<iomanip>#include<numeric>#include<stack>#include<queue>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<bitset>#include<random>#include<functional>#include<utility>#include<atcoder/segtree>using namespace std;template<class T,T (*op)(T,T),T (*e)()> struct SegmentTree{private:int siz;vector<T> node;public:SegmentTree(int n) noexcept{siz = 1;while(siz < n) siz <<= 1;node.assign(2*siz-1,e());}void replace(int pos,T x) noexcept {func_update(pos,x,[](T u,T v){return u = v;});}void add(int pos,T x) noexcept {func_update(pos,x,[](T u,T v){return u+v;});}void func_update(int pos,T x) noexcept {func_update(pos,x,op);}void func_update(int pos,T x,T (*func)(T,T)) noexcept{assert(0 <= pos && pos < siz);pos += siz - 1;node[pos] = func(node[pos],x);while(pos){pos = (pos-1)/2;node[pos] = op(node[2*pos+1],node[2*pos+2]);}}T operator [](int pos) noexcept{assert(0 <= pos && pos < siz);return node[pos+siz-1];}T prod(int l,int r) noexcept{assert(0 <= l && l <= r && r <= siz);l += siz-1;r += siz-1;T Lval = e();T Rval = e();while(l < r){if(!(l & 1)) Lval = op(Lval,node[l++]);if(!(r & 1)) Rval = op(node[--r],Rval);l >>= 1;r >>= 1;}return op(Lval,Rval);}T prod() noexcept {return node[0];}};long long op(long long a,long long b){while(b){a %= b;swap(a,b);}return a;}long long e() {return 0;}int N;void solve(){cin >> N;vector<long long> A(N);for(int i = 0;i < N;i++) cin >> A[i];atcoder::segtree<long long,op,e> seg(A);long long ans = 0;int ri = 0;for(int i = 0;i < N;i++){while(ri <= N){long long g = seg.prod(i,ri);if(g == 1) break;else ri++;}ans += N-ri+1;}cout << ans << endl;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1;//cin >> tt;while(tt--) solve();}