結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:24:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,790 bytes |
コンパイル時間 | 2,898 ms |
コンパイル使用メモリ | 222,888 KB |
最終ジャッジ日時 | 2025-01-10 00:03:43 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 TLE * 6 |
ソースコード
#define _GLIBCXX_DEBUG#include<bits/stdc++.h>using namespace std;#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)#define rrep(i,x) for(ll i = (ll)(x)-1;0 <= i; i--)#define reps(i,x) for(ll i = 1; i < (ll)(x)+1; i++)#define rreps(i,x) for(ll i = (ll)(x); 1 <= i; i--)#define debug(x) cerr << #x << ": " << (x) << "\n";#define all(x) (x).begin(), (x).end()typedef long long ll;typedef long double ld;typedef pair<int,int> P;typedef pair<ll,ll> Pll;typedef vector<ll> vl;typedef vector<vector<ll>> vvl;typedef vector<vector<vector<ll>>> vvvl;const ll INF = numeric_limits<ll>::max()/4;const int n_max = 1e5+10;#define int lltemplate< 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(vector< Monoid > &vec) {for(int i = 0; i < vec.size(); i++)set(i, vec[i]);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;}};template <class T, class U>ll euclid_gcd(T a, U b){if(a < b)return euclid_gcd(b,a);if(b == 0)return a;ll r;while((r = a%b)){a = b;b = r;}return b;}signed main(){cin.tie(nullptr);ios::sync_with_stdio(false);ll n; cin >> n;vector<ll> a(n);rep(i,n) cin >> a[i];auto f = [&](ll a, ll b){return euclid_gcd(a, b);};ll ans = 0;SegmentTree<ll> seg(n, f, 0);seg.build(a);auto c = [](ll x){return x == 1;};rep(i,n){ll id = seg.find_first(i, c);// debug(i);debug(id);if(id != -1)ans += n - id;}cout << ans << endl;}