結果
問題 |
No.1036 Make One With GCD 2
|
ユーザー |
![]() |
提出日時 | 2020-04-25 22:21:27 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 998 ms / 2,000 ms |
コード長 | 3,265 bytes |
コンパイル時間 | 2,126 ms |
コンパイル使用メモリ | 165,248 KB |
実行使用メモリ | 15,352 KB |
最終ジャッジ日時 | 2024-09-16 14:01:53 |
合計ジャッジ時間 | 18,655 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
//#include <bits/stdc++.h> #include "bits/stdc++.h" using namespace std; typedef long long ll; //#include "boost/multiprecision/cpp_int.hpp" //typedef boost::multiprecision::cpp_int LL; typedef long double dd; #define i_7 (ll)(1E9+7) //#define i_7 998244353 #define i_5 i_7-2 ll mod(ll a){ ll c=a%i_7; if(c>=0)return c; return c+i_7; } typedef pair<ll,ll> l_l; typedef pair<dd,dd> d_d; ll inf=(ll)1E16; #define rep(i,l,r) for(ll i=l;i<=r;i++) #define pb push_back ll max(ll a,ll b){if(a<b)return b;else return a;} ll min(ll a,ll b){if(a>b)return b;else return a;} void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]); void Min(ll &pos,ll val){pos=min(pos,val);} void Add(ll &pos,ll val){pos=mod(pos+val);} dd EPS=1E-9; #define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define fi first #define se second #define endl "\n" #define SORT(v) sort(v.begin(),v.end()) #define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end()) #define POSL(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin()) #define POSU(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin()) template<class T> inline bool chmax(T &a, T b) { if(a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T &a, T b) { if(a > b) { a = b; return true; } return false; } ////////////////////////// template<typename T, typename Func_mv> struct Segtree { ll n, n_org; vector<T> dat; Func_mv merge_values; //dataとdataの演算 T te; //dataの単位元かつ初期値 Segtree(){} Segtree(ll n_org, Func_mv merge_values, T te): n_org(n_org), merge_values(merge_values), te(te){ n = 1; while(n < n_org) n <<= 1; dat.resize(2*n-1, te); } void build(vector<T>& A){ for(ll k=0; k<ll(A.size()); k++) dat[k+n-1] = A[k]; for(ll k=n-2; k>=0; k--) dat[k] = merge_values(dat[2*k+1], dat[2*k+2]); } T get(ll a, ll b){ //[a,b]から(最小値とか和とかを)get return query(a, b+1, 0, 0, n); } private: T query(ll a, ll b, ll k, ll lb, ll rb){ if(rb<=a || b<=lb) return te; if(a<=lb && rb<=b) return dat[k]; ll mb = (lb+rb)>>1; T vl = query(a, b, 2*k+1, lb, mb); T vr = query(a, b, 2*k+2, mb, rb); return merge_values(vl, vr); } }; ll gcd(ll a,ll b){ if(a>b)swap(a,b); if(a==0)return b; return gcd(b%a,a); } auto make_segtree = [](ll N){ //点更新と区間和 using T=ll; auto merge_values=[](T&a,T&b){return gcd(a,b);}; T te=0; return Segtree<T, decltype(merge_values)> (N, merge_values, te); }; /* auto st = make_segtree(n); vector<ll> init(n); st.build(init); */ int main(){fastio ll n;cin>>n; auto st = make_segtree(n); vector<ll> init(n); rep(i,0,n-1)cin>>init[i]; st.build(init); ll ans=0; ll ng=-1; rep(i,0,n-1){ chmax(ng,i-1); while(ng<=n-2){ if(st.get(i,ng+1)==1){ break; }else{ ng++; } } ll ok=ng+1; ans+=n-ok; } cout<<ans<<endl; return 0; }