結果
問題 | No.1036 Make One With GCD 2 |
ユーザー | suta28407928 |
提出日時 | 2020-04-25 17:12:01 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,068 ms / 2,000 ms |
コード長 | 3,941 bytes |
コンパイル時間 | 983 ms |
コンパイル使用メモリ | 88,132 KB |
実行使用メモリ | 15,300 KB |
最終ジャッジ日時 | 2023-10-14 19:55:31 |
合計ジャッジ時間 | 19,393 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 617 ms
15,280 KB |
testcase_01 | AC | 245 ms
15,220 KB |
testcase_02 | AC | 466 ms
15,224 KB |
testcase_03 | AC | 39 ms
8,596 KB |
testcase_04 | AC | 66 ms
13,704 KB |
testcase_05 | AC | 1 ms
4,372 KB |
testcase_06 | AC | 2 ms
4,372 KB |
testcase_07 | AC | 98 ms
8,748 KB |
testcase_08 | AC | 81 ms
8,508 KB |
testcase_09 | AC | 397 ms
14,916 KB |
testcase_10 | AC | 372 ms
14,784 KB |
testcase_11 | AC | 405 ms
15,148 KB |
testcase_12 | AC | 376 ms
15,036 KB |
testcase_13 | AC | 669 ms
14,928 KB |
testcase_14 | AC | 680 ms
14,940 KB |
testcase_15 | AC | 636 ms
14,772 KB |
testcase_16 | AC | 644 ms
14,696 KB |
testcase_17 | AC | 662 ms
14,932 KB |
testcase_18 | AC | 2 ms
4,372 KB |
testcase_19 | AC | 2 ms
4,372 KB |
testcase_20 | AC | 3 ms
4,368 KB |
testcase_21 | AC | 3 ms
4,372 KB |
testcase_22 | AC | 630 ms
14,832 KB |
testcase_23 | AC | 463 ms
13,632 KB |
testcase_24 | AC | 652 ms
14,920 KB |
testcase_25 | AC | 595 ms
14,576 KB |
testcase_26 | AC | 619 ms
14,736 KB |
testcase_27 | AC | 2 ms
4,372 KB |
testcase_28 | AC | 1 ms
4,372 KB |
testcase_29 | AC | 2 ms
4,368 KB |
testcase_30 | AC | 2 ms
4,372 KB |
testcase_31 | AC | 2 ms
4,372 KB |
testcase_32 | AC | 2 ms
4,368 KB |
testcase_33 | AC | 1 ms
4,372 KB |
testcase_34 | AC | 1 ms
4,372 KB |
testcase_35 | AC | 1 ms
4,372 KB |
testcase_36 | AC | 2 ms
4,372 KB |
testcase_37 | AC | 2 ms
4,368 KB |
testcase_38 | AC | 460 ms
15,280 KB |
testcase_39 | AC | 1,068 ms
15,144 KB |
testcase_40 | AC | 463 ms
13,632 KB |
testcase_41 | AC | 772 ms
15,256 KB |
testcase_42 | AC | 767 ms
15,204 KB |
testcase_43 | AC | 718 ms
15,300 KB |
testcase_44 | AC | 762 ms
15,220 KB |
ソースコード
#include <iostream> #include <string> #include <cstdlib> #include <cmath> #include <vector> #include <map> #include <set> #include <algorithm> #include <queue> #include <stack> #include <functional> #include <bitset> #include <assert.h> using namespace std; typedef long long ll; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<char> vc; typedef vector<string> vs; typedef vector<bool> vb; typedef vector<double> vd; typedef pair<ll,ll> P; typedef vector<P> vpl; typedef tuple<ll,ll,ll> tapu; #define rep(i,n) for(ll i=0; i<(n); i++) #define REP(i,a,b) for(int i=(a); i<(b); i++) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() const int inf = 1<<30; const ll linf = 1LL<<62; const int MAX = 510000; ll dy[8] = {0,1,0,-1,1,-1,1,-1}; ll dx[8] = {1,0,-1,0,1,-1,-1,1}; const double pi = acos(-1); const double eps = 1e-7; template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){ if(a>b){ a = b; return true; } else return false; } template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){ if(a<b){ a = b; return true; } else return false; } template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";} template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){ cout << a << " " << b << " " << c << "\n"; } const int mod = 1e9 + 7; //const int mod = 998244353; template< typename Monoid > struct SegmentTree { using F = function< Monoid(Monoid, Monoid) >; int sz; vector< Monoid > seg; const F f; const Monoid M1; SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void set(int k, const Monoid &x) { seg[k + sz] = x; } void build() { for(int k = sz - 1; k > 0; k--) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } void update(int k, const Monoid &x) { k += sz; seg[k] = x; while(k >>= 1) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } Monoid query(int a, int b) { Monoid L = M1, R = M1; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if(a & 1) L = f(L, seg[a++]); if(b & 1) R = f(seg[--b], R); } return f(L, R); } Monoid operator[](const int &k) const { return seg[k + sz]; } template< typename C > int find_subtree(int a, const C &check, Monoid &M, bool type) { while(a < sz) { Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]); if(check(nxt)) a = 2 * a + type; else M = nxt, a = 2 * a + 1 - type; } return a - sz; } template< typename C > int find_first(int a, const C &check) { Monoid L = M1; if(a <= 0) { if(check(f(L, seg[1]))) return find_subtree(1, check, L, false); return -1; } int b = sz; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if(a & 1) { Monoid nxt = f(L, seg[a]); if(check(nxt)) return find_subtree(a, check, L, false); L = nxt; ++a; } } return -1; } template< typename C > int find_last(int b, const C &check) { Monoid R = M1; if(b >= sz) { if(check(f(seg[1], R))) return find_subtree(1, check, R, true); return -1; } int a = sz; for(b += sz; a < b; a >>= 1, b >>= 1) { if(b & 1) { Monoid nxt = f(seg[--b], R); if(check(nxt)) return find_subtree(b, check, R, true); R = nxt; } } return -1; } }; ll GCD(ll a, ll b){ if(b==0) return a; else return GCD(b,a%b); } int main(){ ll n; cin >> n; vl a(n); rep(i,n) cin >> a[i]; SegmentTree<ll> seg(n,[](ll a, ll b){return GCD(a,b);},0); rep(i,n) seg.set(i,a[i]); seg.build(); ll right = 0; ll ans = 0; rep(i,n){ ll gc = seg.query(i,right+1); while(right < n){ gc = GCD(gc,a[right]); if(gc == 1) break; right++; } ans += n - right; if(i==right) right++; } cout << ans << endl; }