Untitled
#include <bits/stdc++.h> #define ll long long #define II pair<int, int> #define fs first #define sc second #define endl '\n' #define mp(x, y) make_pair(x, y) #define sz(x) ((int) (x.size())) #define forlr(i, l, r) for(int i = l; i <= r; ++i) #define forrl(i, r, l) for(int i = r; i >= l; --i) #define show(v) for(auto i : v) cout << i << " "; cout << endl; #define showlr(v, l, r) for (int i = l; i <= r; i++) cout << v[i] << " "; cout << endl; #define all(v) v.begin(), v.end() #define Unique(v) v.erase(unique(all(v)), v.end()); const long long LINF = 1ll << 60; const int INF = 1 << 30; const int N = 2e5 + 5; using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, k; int a[N], pre[N], L[N], R[N]; vector<int> divs[N]; namespace BRUTE { void solve() { int ans = 0; forlr(i, 1, n) { int M = INF, S = 0; forlr(j, i, n) { M = min(M, a[j]); S += a[j]; int v = __gcd(M, S); if(M + S == v * k) ans++; } } cout << ans << endl; } } namespace FULL { int ans = 0; inline void dnc(int l, int r) { if(l == r) return; int mid = (l + r) >> 1; int mn = mid + 1; forlr(i, mid + 1, r) { if(a[i] < a[mn]) mn = i; int Left = max(l, L[mn]), Right = mid; for(int v : divs[a[mn]]) { if(Left > Right) break; int sum = a[mn] / v * (k - v); int x = lower_bound(pre + Left - 1, pre + Right - 1, pre[i] - sum) - pre; Right = x; if(pre[i] - pre[x] == sum) ans++; else Right++; } } mn = mid; forrl(i, mid, l) { if(a[i] < a[mn]) mn = i; int Left = mid + 1, Right = min(r, R[mn]); for(int v : divs[a[mn]]) { if(Left > Right) break; int sum = a[mn] / v * (k - v); int x = lower_bound(pre + Left, pre + Right, pre[i - 1] + sum) - pre; Left = x; if(pre[x] - pre[i - 1] == sum) ans++; } } dnc(l, mid); dnc(mid + 1, r); } void solve() { dnc(1, n); cout << ans << endl; } } inline void create_divisors() { forrl(i, k / 3, 1) { if(__gcd(i, k - i) != 1) continue; for(int j = i; j <= 100000; j += i) { divs[j].push_back(i); } } } inline void show_divisors() { int mx = 0; forlr(i, 1, 100000) { if(sz(divs[i]) > mx) { mx = sz(divs[i]); cout << i << " " << mx << endl; } } } inline void create_monotonic_stacks() { stack<int> st; forlr(i, 1, n) { while(!st.empty() && a[st.top()] >= a[i]) st.pop(); L[i] = st.empty() ? 1 : st.top() + 1; st.push(i); } while(!st.empty()) st.pop(); forrl(i, n, 1) { while(!st.empty() && a[st.top()] > a[i]) st.pop(); R[i] = st.empty() ? n : st.top() - 1; st.push(i); } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("A.INP", "r", stdin); // freopen("A.OUT", "w", stdout); cin >> n >> k; forlr(i, 1, n) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; } create_monotonic_stacks(); create_divisors(); // show_divisors(); FULL::solve(); // BRUTE::solve(); return 0; }
Leave a Comment