結果
問題 | No.1036 Make One With GCD 2 |
ユーザー | Mi |
提出日時 | 2020-04-24 22:39:03 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 954 ms / 2,000 ms |
コード長 | 2,855 bytes |
コンパイル時間 | 1,716 ms |
コンパイル使用メモリ | 172,108 KB |
実行使用メモリ | 15,376 KB |
最終ジャッジ日時 | 2023-10-14 19:27:47 |
合計ジャッジ時間 | 17,830 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 528 ms
15,116 KB |
testcase_01 | AC | 225 ms
15,056 KB |
testcase_02 | AC | 347 ms
15,208 KB |
testcase_03 | AC | 45 ms
8,504 KB |
testcase_04 | AC | 79 ms
13,980 KB |
testcase_05 | AC | 2 ms
4,352 KB |
testcase_06 | AC | 1 ms
4,348 KB |
testcase_07 | AC | 77 ms
8,772 KB |
testcase_08 | AC | 63 ms
8,400 KB |
testcase_09 | AC | 386 ms
15,376 KB |
testcase_10 | AC | 361 ms
14,960 KB |
testcase_11 | AC | 396 ms
15,224 KB |
testcase_12 | AC | 364 ms
14,764 KB |
testcase_13 | AC | 568 ms
14,948 KB |
testcase_14 | AC | 577 ms
14,852 KB |
testcase_15 | AC | 540 ms
14,608 KB |
testcase_16 | AC | 545 ms
14,912 KB |
testcase_17 | AC | 561 ms
14,912 KB |
testcase_18 | AC | 2 ms
4,356 KB |
testcase_19 | AC | 2 ms
4,352 KB |
testcase_20 | AC | 3 ms
4,352 KB |
testcase_21 | AC | 3 ms
4,348 KB |
testcase_22 | AC | 533 ms
14,528 KB |
testcase_23 | AC | 393 ms
13,932 KB |
testcase_24 | AC | 554 ms
14,952 KB |
testcase_25 | AC | 504 ms
14,600 KB |
testcase_26 | AC | 524 ms
14,680 KB |
testcase_27 | AC | 2 ms
4,352 KB |
testcase_28 | AC | 2 ms
4,348 KB |
testcase_29 | AC | 2 ms
4,352 KB |
testcase_30 | AC | 1 ms
4,348 KB |
testcase_31 | AC | 1 ms
4,352 KB |
testcase_32 | AC | 2 ms
4,352 KB |
testcase_33 | AC | 2 ms
4,352 KB |
testcase_34 | AC | 2 ms
4,348 KB |
testcase_35 | AC | 1 ms
4,352 KB |
testcase_36 | AC | 1 ms
4,352 KB |
testcase_37 | AC | 1 ms
4,368 KB |
testcase_38 | AC | 348 ms
15,056 KB |
testcase_39 | AC | 954 ms
15,228 KB |
testcase_40 | AC | 392 ms
13,928 KB |
testcase_41 | AC | 647 ms
15,208 KB |
testcase_42 | AC | 643 ms
15,116 KB |
testcase_43 | AC | 611 ms
15,212 KB |
testcase_44 | AC | 649 ms
15,116 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> P; typedef pair<int,int> Pi; #define rep(i,n) for(ll i=0;i<n;i++) #define FOR(i,a,b) for(ll i=a;i<b;i++) #define fi first #define se second #define endl "\n" template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;} template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;} template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";} template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";} template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;} template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;} template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;} template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;} const ll mod=1e9+7; const ll inf=1e17; const int INF=1e9; const double PI=acos(-1); const double EPS=1e-10; //a,bの最大公約数 template <class T> T gcd(T a,T b) { if (b==0) return a; else return gcd(b,a%b); } template<typename Monoid,typename F> struct SegmentTree{ int sz; vector<Monoid> node; const F op;//演算 const Monoid e;//単位元 SegmentTree(int n,const F op,const Monoid &e):op(op),e(e){ sz=1; while(sz<n) sz*=2; node.assign(2*sz,e); } void build(const vector<Monoid> &v){ int n=v.size(); for(int i=0;i<n;i++) node[i+sz-1]=v[i]; for(int i=sz-2;i>=0;i--) node[i]=op(node[2*i+1],node[2*i+2]); } void update(int k,const Monoid &x){ k+=sz-1; node[k]=x; while(k>0){ k=(k-1)/2; node[k]=op(node[2*k+1],node[2*k+2]); } } Monoid query(int a,int b,int k=0,int l=0,int r=-1){ if(r<0) r=sz; if(r<=a || b<=l) return e; if(a<=l && r<=b) return node[k]; else{ Monoid vl=query(a,b,2*k+1,l,(l+r)/2); Monoid vr=query(a,b,2*k+2,(l+r)/2,r); return op(vl,vr); } } Monoid operator[](const int &k)const{ return node[k+sz-1]; } }; int main(){ cin.tie(0);ios::sync_with_stdio(false); ll n; cin>>n; vector<ll> a(n); rep(i,n){ cin>>a[i]; } auto op=[](ll a,ll b){return gcd(a,b);}; SegmentTree<ll,decltype(op)> seg(n,op,0); seg.build(a); ll ans=0,r=0,now=0; rep(l,n){ while(r<n && now!=1){ now=gcd(now,a[r]); r++; } if(now==1){ ans+=n-r+1; } now=seg.query(l+1,r); } cout<<ans<<endl; }