結果
問題 | 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;}}