結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
|
提出日時 | 2021-08-02 20:51:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 198 ms / 2,000 ms |
コード長 | 2,003 bytes |
コンパイル時間 | 2,604 ms |
コンパイル使用メモリ | 222,556 KB |
最終ジャッジ日時 | 2025-01-23 13:44:12 |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#pragma GCC optimize("Ofast")#include <bits/stdc++.h>using namespace std;typedef long long int ll;typedef unsigned long long ull;mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());ll myRand(ll B) {return (ull)rng() % B;}long long binary_gcd(long long a, long long b) {if (a == 0) return b;if (b == 0) return a;const int n = __builtin_ctzll(a | b);a >>= __builtin_ctzll(a);while (b > 0) {b >>= __builtin_ctzll(b);if (a > b) swap(a, b);b -= a;}return a << n;}template<class S, S (*op)(S, S), S (*e)()> struct swag {std::stack<std::pair<S, S>> front_stack, back_stack;swag() {front_stack.emplace(e(), e());back_stack.emplace(e(), e());}bool empty() const { return front_stack.size() == 1 && back_stack.size() == 1; }size_t size() const { return front_stack.size() + back_stack.size() - 2; }S fold() const { return op(front_stack.top().second, back_stack.top().second); }void push(const S& x) { back_stack.emplace(x, op(back_stack.top().second, x)); }void pop() {assert(front_stack.size() > 1 || back_stack.size() > 1);if (front_stack.size() > 1) {front_stack.pop();} else {while (back_stack.size() > 2) {front_stack.emplace(back_stack.top().first, op(front_stack.top().second, back_stack.top().first));back_stack.pop();}back_stack.pop();}}};long long e() { return 0; }int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n; cin >> n;vector<ll> a(n);for(int i=0;i<n;i++){cin >> a[i];}ll res=0;a.push_back(1);swag<ll, binary_gcd, e> q;for (int l = 0, r = 0; l < n; ++l) {while(r <= n and q.fold() != 1) {q.push(a[r]);r++;}if(r <= n) res += n-(r-1);q.pop();}printf("%lld\n",res);}