結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:34:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,982 bytes |
コンパイル時間 | 2,834 ms |
コンパイル使用メモリ | 185,544 KB |
実行使用メモリ | 26,112 KB |
最終ジャッジ日時 | 2024-11-07 02:46:52 |
合計ジャッジ時間 | 10,968 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 4 |
other | TLE * 1 -- * 40 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma region Macros #include <bits/stdc++.h> using namespace std; //#include <boost/multiprecision/cpp_int.hpp> //using multiInt = boost::multiprecision::cpp_int; using ll = long long int; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; using pld = pair<ld, ld>; template <typename Q_type> using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>; constexpr int MOD_TYPE = 1; constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353); constexpr int INF = (int)1e9; constexpr ll LINF = (ll)4e18; constexpr ld PI = acos(-1.0); constexpr ld EPS = 1e-11; constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0}; constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0}; #define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i) #define rep(i, n) REP(i, 0, n) #define MP make_pair #define MT make_tuple #define YES(n) cout << ((n) ? "YES" : "NO") << "\n" #define Yes(n) cout << ((n) ? "Yes" : "No") << "\n" #define possible(n) cout << ((n) ? "possible" : "impossible") << "\n" #define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n" #define Yay(n) cout << ((n) ? "Yay!" : ":(") << "\n" #define all(v) v.begin(), v.end() #define NP(v) next_permutation(all(v)) #define dbg(x) cerr << #x << ":" << x << "\n"; #pragma endregion ll temp; inline ll gcd(ll a, ll b) { if (a < b) swap(a, b); while (b != 0) { temp = b; b = a % b; a = temp; } return a; } template <typename T> class SegmentTree { private: int N; vector<T> dat; public: SegmentTree(vector<T> &v) { init(v); } void init(vector<T> &v) { N = 1; int sz = v.size(); while (N < sz) N *= 2; dat.resize(2 * N - 1); for (int i = 0; i < N; ++i) dat[i + N - 1] = (i < sz ? v[i] : 0); for (int i = N - 2; i >= 0; --i) dat[i] = gcd(dat[i * 2 + 1], dat[i * 2 + 2]); } void update(int k, T a) { k += N - 1; dat[k] = a; while (k > 0) { k = (k - 1) / 2; dat[k] = gcd(dat[k * 2 + 1], dat[k * 2 + 2]); } } T query(int a, int b) { ll val_left = 0; ll val_right = 0; for (a += (N - 1), b += (N - 1); a < b; a >>= 1, b >>= 1) { if ((a & 1) == 0) { val_left = gcd(val_left, dat[a]); } if ((b & 1) == 0) { val_right = gcd(val_right, dat[--b]); } } return gcd(val_left, val_right); } }; int main() { /* cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(30) << setiosflags(ios::fixed); */ ll n; cin >> n; vector<ll> a(n); rep(i, n) scanf("%lld", &a[i]); SegmentTree<ll> sg(a); ll ans = (n + 1) * n / 2; int lo, hi, mi; rep(i, n) { lo = i, hi = n + 1; while (hi - lo > 1) { mi = (lo + hi) / 2; if (sg.query(i, mi) > 1) lo = mi; else hi = mi; } ans -= (lo - i); } printf("%lld\n", ans); return 0; }