結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:45:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,078 ms / 2,000 ms |
コード長 | 1,402 bytes |
コンパイル時間 | 1,869 ms |
コンパイル使用メモリ | 169,428 KB |
実行使用メモリ | 15,360 KB |
最終ジャッジ日時 | 2024-09-16 13:26:56 |
合計ジャッジ時間 | 19,675 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<long long> segtree(vector<long long> &A){ int N = 1; while (N < A.size()){ N = N * 2; } vector<long long> ST(N * 2 - 1); for (int i = 0; i < A.size(); i++){ ST[i + N - 1] = A[i]; } for (int i = A.size() + N - 1; i < N * 2 - 1; i++){ ST[i] = 0; } for (int i = N - 2; i >= 0; i--){ ST[i] = __gcd(ST[i * 2 + 1], ST[i * 2 + 2]); } return ST; } long long segtree_query(vector<long long> &ST, int x, int y, int i, int L, int R){ if (y <= L || R <= x){ return 0; } else if (x <= L && R <= y){ return ST[i]; } else { int M = (L + R) / 2; long long A = segtree_query(ST, x, y, i * 2 + 1, L, M); long long B = segtree_query(ST, x, y, i * 2 + 2, M, R); return __gcd(A, B); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector<long long> A(N); for (int i = 0; i < N; i++){ cin >> A[i]; } vector<long long> ST = segtree(A); if (ST[0] != 1){ cout << 0 << endl; } else { int X = (ST.size() + 1) / 2; long long ans = 0; int L = 0; int R = 0; while (1){ while (R < N){ if (segtree_query(ST, L, R + 1, 0, 0, X) == 1){ break; } R++; if (R > N){ R--; break; } } ans += N - R; L++; if (L >= N){ break; } } cout << ans << endl; } }