結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-07-08 03:15:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,558 bytes |
コンパイル時間 | 2,954 ms |
コンパイル使用メモリ | 242,640 KB |
最終ジャッジ日時 | 2025-01-11 16:48:51 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 TLE * 6 |
ソースコード
#pragma GCC optimize("Ofast")#include <bits/stdc++.h>#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>using namespace std;using namespace __gnu_pbds;using ll = long long;using u64 = uint_fast64_t;using pii = pair<int, int>;using pll = pair<long long, long long>;#define rep(i, n) for(int i = 0; i < (n); ++i)#define all(x) (x).begin(),(x).end()constexpr char ln = '\n';constexpr long long MOD = 1000000007;//constexpr long long MOD = 998244353;template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true;} return false; }template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true;} return false; }inline int popcount(int x) {return __builtin_popcount(x);}inline int popcount(long long x) {return __builtin_popcountll(x);}void print() { cout << "\n"; }template<class T, class... Args>void print(const T &x, const Args &... args) {cout << x << " ";print(args...);}///////////////////////////////////////////////////////////////////////////////////////////////////////////////template<typename T, typename Monoid>struct SegmentTree {Monoid merge;T unity;int N;vector<T> node;SegmentTree(Monoid f, T id) : merge(f), unity(id) {}void init(int sz) {N = 1;while (N < sz) N <<= 1;node.assign(2*N,unity);}void set(int k, const T &val) {node[k+N] = val;}void build() {for (int i = N-1; i > 0; --i) {node[i] = merge(node[i<<1|0], node[i<<1|1]);}}// (0-indexed)void update(int x, T val) {x += N;node[x] = val;while (x > 1) {x >>= 1;node[x] = merge(node[x<<1|0], node[x<<1|1]);}}// [l, r) (0-indexed)T get(int l, int r) {if (l >= r) return unity;T resl = unity, resr = unity;l += N; r += N;while (l < r) {if (l & 1) resl = merge(resl, node[l++]);l >>= 1;if (r & 1) resr = merge(node[--r], resr);r >>= 1;}return merge(resl, resr);}template<typename C>int binarysearch(int s, const C &check, T &acc, int k, int l, int r) {if (r-l==1) {acc = merge(acc,node[k]);return check(acc) ? k - N : -1;}int m = (l+r)>>1;if(m <= s) return binarysearch(s, check, acc, (k<<1)|1, m, r);if(s <= l && !check(merge(acc,node[k]))) {acc = merge(acc,node[k]);return -1;}int vl = binarysearch(s, check, acc, (k<<1)|0, l, m);if(~vl) return vl;return binarysearch(s, check, acc, (k<<1)|1, m, r);}template<typename C>int binarysearch(int s, const C &check) {T acc = unity;return binarysearch(s, check, acc, 1, 0, N);}T operator[](int x) {return node[x+N];}};ll _gcd(ll a, ll b) {while (a) {ll tmp = a;a = b%a;b = tmp;}return b;}int main() {ios::sync_with_stdio(false); cin.tie(nullptr);int N; cin >> N;vector<ll> A(N);rep(i,N) cin >> A[i];auto f=[](ll a, ll b) {return _gcd(a,b);};const ll id = 0;SegmentTree seg(f,id);seg.init(N);rep(i,N) seg.set(i,A[i]);seg.build();auto check=[](ll x) {return x==1;};ll ans = 0;rep(i,N) {int k = seg.binarysearch(i,check);if (k==-1) continue;ans += N-k;}cout << ans << ln;}