fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define ll long long int
  5. int main() {
  6.     ios_base::sync_with_stdio(false);
  7.     cin.tie(NULL);
  8.     ll t;
  9.     cin >> t;
  10.     while (t--) {
  11.         ll n;
  12.         ll x;
  13.         cin >> n >> x;
  14.         ll arr[n];
  15.         for (ll i = 0; i < n; i++) {
  16.             cin >> arr[i];
  17.         }
  18.         vector < ll > factors;
  19.         for (ll i = 1; i * i <= x; i++) {
  20.  
  21.             if (x % i == 0) {
  22.                 if (i <= n) {
  23.                     factors.push_back(i);
  24.                 }
  25.                 ll val = x / i;
  26.                 if (i != val) {
  27.                     if (val <= n) {
  28.                         factors.push_back(val);
  29.                     }
  30.                 }
  31.             }
  32.         }
  33.         ll sz = factors.size();
  34.         ll ans = 0;
  35.         ll starti = 0;
  36.         ll startj = 0;
  37.         ll prefix[n];
  38.         prefix[0] = arr[0];
  39.         for (ll i = 1; i < n; i++) {
  40.             prefix[i] = prefix[i - 1] + arr[i];
  41.         }
  42.         for (ll i = 0; i < sz; i++) {
  43.             // factor by factor
  44.             ll sidelength = factors[i];
  45.             //  cout<<"S:"<<sidelength<<endl;
  46.             ll y = x / sidelength;
  47.             ll sumi = 0;
  48.             ll sumj = 0;
  49.             map < ll, ll > m;
  50.             for (ll r = 0; r < n - sidelength + 1; r++) {
  51.                 ll val6 = r + sidelength - 1;
  52.                 if (r - 1 < 0) {
  53.                     ll val7 = prefix[val6];
  54.                     m[val7]++;
  55.                 } else {
  56.                     ll valy = prefix[val6] - prefix[r - 1];
  57.                     m[valy]++;
  58.                 }
  59.             }
  60.             for (ll i1 = starti; i1 < n - sidelength + 1; i1++) {
  61.                 ll endi = i1 + sidelength - 1;
  62.                 //    cout<<"Si:"<<i1<<"Ei:"<<endi<<endl;
  63.                 if (i1 - 1 < 0) {
  64.                     sumi = prefix[endi];
  65.                 } else {
  66.                     sumi = prefix[endi] - prefix[i1 - 1];
  67.                 }
  68.                 ll remsum = y - sumi;
  69.                 map < ll, ll > ::iterator it = m.find(remsum);
  70.                 if (it != m.end()) {
  71.                     ans = ans + it->second;
  72.                 }
  73.             }
  74.  
  75.         }
  76.         cout << ans << endl;
  77.  
  78.     }
  79.  
  80.     return 0;
  81. }
Success #stdin #stdout 0s 4424KB
comments (?)
stdin 
2
5 36
1 2 3 1 12
4 54
3 3 3 3
stdout 
6
4
https://ideone.com/ZtKgZ6
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!