結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:32:59 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 440 ms / 2,000 ms |
コード長 | 1,381 bytes |
コンパイル時間 | 6,467 ms |
コンパイル使用メモリ | 164,080 KB |
実行使用メモリ | 15,360 KB |
最終ジャッジ日時 | 2024-09-16 13:23:55 |
合計ジャッジ時間 | 18,759 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i=0; i<n; i++)#define pb push_back#define int long longint N;int A[500100];struct segtree {int size;vector<int> node;segtree(int n) {size = 1;while (size<n) size *= 2;node.resize(2*size-1);fill(node.begin(), node.end(), 0);}void update(int k, int a) {k += size-1;node[k] = a;while (k>0) {k = (k-1)/2;node[k] = gcd(node[2*k+1], node[2*k+2]);}}int query(int a, int b, int k, int l, int r) {if (r<=a || b<=l) return 0;if (a<=l && r<=b) return node[k];else {int vl = query(a, b, 2*k+1, l, (l+r)/2);int vr = query(a, b, 2*k+2, (l+r)/2, r);return gcd(vl, vr);}}int get(int a, int b) {return query(a, b, 0, 0, size);}};signed main() {cin.tie(0); ios::sync_with_stdio(false);cin >> N;rep(i, N) cin >> A[i];segtree st(N);rep(i, N) st.update(i, A[i]);int ans = 0;int G = 0;int r = 0;rep(l, N) {while (r<N && gcd(G, A[r])>1) {G = gcd(G, A[r]);r++;}ans += N-r;if (l==r) r++;else G = st.get(l+1, r);}cout << ans << endl;}