結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
|
提出日時 | 2020-04-24 21:42:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 624 ms / 2,000 ms |
コード長 | 1,387 bytes |
コンパイル時間 | 2,715 ms |
コンパイル使用メモリ | 205,612 KB |
最終ジャッジ日時 | 2025-01-09 23:24:02 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<typename T>struct SparseTable{vector<vector<T>> dat;vector<int> lookup;typedef function<T(T a, T b)> Func;Func f;T e;SparseTable(){}SparseTable(const vector<T> &v, Func f, T e){ initialize(v, f, e); }void initialize(const vector<T> &v, Func fin, T ein){f = fin;e = ein;int b = 0;while((1<<b) <= v.size()) b++;int N = 1<<b;dat.assign(b, vector<T>(N, e));for(int i=0; i<v.size(); i++) dat[0][i] = v[i];for(int i=1; i<b; i++){int d = 1<<i;for(int j=0; j+d<=N; j++){dat[i][j] = f(dat[i-1][j], dat[i-1][j+d/2]);}}lookup.assign(N+1, 0);for(int i=2; i<=N; i++){lookup[i] = lookup[i>>1] + 1;}}T between(int l, int r) {if(l > r) return e;r++;int b = lookup[r-l];return f(dat[b][l], dat[b][r-(1<<b)]);}};int main(){int N;cin >> N;vector<int64_t> A(N);for(int i=0; i<N; i++) cin >> A[i];SparseTable<int64_t> st(A, [](auto a, auto b){ return gcd(a, b); }, 0);int r = 0;int64_t ans = 0;for(int l=0; l<N; l++){while(r < N && st.between(l, r) != 1) r++;ans += N-r;}cout << ans << endl;return 0;}