結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
👑 |
提出日時 | 2022-07-09 15:46:03 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 845 bytes |
コンパイル時間 | 12,199 ms |
コンパイル使用メモリ | 283,504 KB |
最終ジャッジ日時 | 2025-01-30 05:56:55 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 TLE * 15 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include<bits/stdc++.h>#include<atcoder/segtree>using namespace std;using namespace atcoder;using S = long long;map<pair<S, S>, S> memo;S op(S x, S y){if(memo.count({x, y})) return memo[{x, y}];if(x > y) swap(x, y);if(x == 0) return y;return memo[{x, y}] = op(y % x, x);}S e(){ return 0; }bool f(S x){return x != 1;}void solve(){int n;cin >> n;vector<long long> A(n);for(int i = 0; i < n; i++) cin >> A[i];segtree<S, op, e> seg(A);long long ans = 0;for(int r = 1; r <= n; r++){int l = seg.min_left(r, f);ans += l;}cout << ans << "\n";}int main(){cin.tie(0)->sync_with_stdio(0);int t;t = 1;//cin >> t;while(t--) solve();}