結果
問題 | No.1036 Make One With GCD 2 |
ユーザー | Enjapma_kyopro |
提出日時 | 2020-06-01 15:34:53 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,838 bytes |
コンパイル時間 | 3,874 ms |
コンパイル使用メモリ | 181,288 KB |
実行使用メモリ | 27,924 KB |
最終ジャッジ日時 | 2023-08-14 02:44:01 |
合計ジャッジ時間 | 16,647 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
ソースコード
#include <bits/stdc++.h> #include <unistd.h> #include <sys/time.h> #include <stdlib.h> using namespace std; typedef long long ll; typedef pair<ll,ll> P; typedef pair<P, ll> T; typedef pair<long double , ll> Ps; const ll INF = 2e18; const ll fact_table = 3200008; long double Pi = 3.1415926535897932384626; priority_queue <ll> pql; priority_queue <P> pqp; priority_queue <P> bag; //big priority queue priority_queue <ll,vector<ll>,greater<ll> > pqls; priority_queue <P,vector<P>,greater<P> > pqps; //small priority queue //top pop ll dx[8]={1,0,-1,0,1,1,-1,-1}; ll dy[8]={0,1,0,-1,1,-1,-1,1}; char dir[] = "DRUL"; //↓,→,↑,← #define endl "\n" #ifdef ENJAPMA #undef endl #endif #define p(x) cout<<x<<endl; #define el cout<<endl; #define pe(x) cout<<x<<" "; #define ps(x) cout<<fixed<<setprecision(25)<<x<<endl; #define pu(x) cout<<(x); #define pb push_back #define lb lower_bound #define ub upper_bound #define CLEAR(a) a = decltype(a)(); #define pc(x) cout << x << ","; #define rep(i, n) for (ll i = 0; i < (n); i ++) // const ll mod = 998244353ll; const ll mod = 1000000007ll; ll mypow(ll a, ll b, ll mod){ll x=1;while(b){while(!(b&1)){(a*=a)%=mod;b>>=1;}(x*=a)%=mod;b--;}return x;} void YES(bool cond){ if(cond){ p("YES");}else{ p("NO");} return;} void Yes(bool cond){ if(cond){ p("Yes");}else{ p("No");} return;} ll mygcd(ll a, ll b){ if (a < b) swap(a, b); if (a == b || b == 0) return a; return mygcd(b, a % b); } struct SegmentTree { //SegmentTree seg( vector<ll>(l + 5, INF) ); private: ll n; vector<ll> node; public: SegmentTree(vector<ll> v) { ll sz = v.size(); n = 1; while(n < sz) n *= 2; node.resize(2*n-1, INF); for(int i=0; i<sz; i++) node[i+n-1] = v[i]; for(int i=n-2; i>=0; i--) node[i] = mygcd(node[2*i+1], node[2*i+2]); } void update(ll x, ll val) { //a[x]をyに更新(小さい方に更新) x += (n - 1); node[x] = val; while(x > 0) { x = (x - 1) / 2; node[x] = mygcd(node[2*x+1], node[2*x+2]); } } ll getgcd(int a, int b, int k=0, int l=0, int r=-1){ // [a, b) の全てについて累積和をとる if (r < 0) r = n; if (r <= a || b <= l) return 0ll; if (a <= l && r <= b) return node[k]; ll vl = getgcd(a, b, 2*k+1, l, (l+r)/2); ll vr = getgcd(a, b, 2*k+2, (l+r)/2, r); return mygcd(vl, vr); } }; /* ll fact[fact_table + 5],rfact[fact_table + 5]; void c3_init(){ fact[0] = rfact[0] = 1; for(ll i=1; i<=fact_table; i++){ fact[i] = (fact[i-1]*i) % mod; } rfact[fact_table] = mypow(fact[fact_table],mod - 2, mod); for(ll i=fact_table; i>=1; i--){ rfact[i-1] = rfact[i] * i; rfact[i-1] %= mod; } return;} ll c3(ll n,ll r){ return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;} */ bool multicase = false; ll n,m,num,a,b,c,d,e,h,q; ll w, k, ans; ll x[500005], y[500005], z[500005]; ll dp[5005][5005]; string s; void solve(){ cin >> n; vector<ll> v; for(ll i=0;i<n;i++){ cin >> a; v.pb(a); } SegmentTree seg(v); ll ans = 0; for(ll i=0;i<n;i++){ ll ok = i, ng = n + 1; while(ng - ok > 1){ ll mid = (ng + ok) / 2; if(seg.getgcd(i, mid) == 1){ ng = mid; }else{ ok = mid; } } ans += n - ok; } p(ans); return; } int main(){ // init(); ios::sync_with_stdio(false); cin.tie(nullptr); ll q, testcase = 1; if(multicase){ cin >> q; }else{ q = 1; } while(q--){ // pu("Case ");pu("#");pu(testcase);pu(": "); solve(); testcase++; } // solve(); return 0; }