fork download 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. #define pb emplace_back
  12. #define fi first
  13. #define se second
  14. #define sz(s) (int)s.size()
  15. #define all(s) (s).begin(), (s).end()
  16. #define ms(a,x) memset(a, x, sizeof (a))
  17. #define cn continue
  18. #define re exit(0)
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef vector<int> vi;
  24. typedef vector<ll> vll;
  25. typedef pair<int, int> pii;
  26. typedef pair<ll, ll> pll;
  27. typedef vector<pii> vpii;
  28. typedef vector<pll> vpll;
  29.  
  30. const int mod=1e9+7;
  31. const int maxn=2e5+15;
  32. const ll inf=4e18;
  33.  
  34. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  35. ll ran(ll l, ll r)
  36. {
  37.     return uniform_int_distribution<ll> (l, r)(rng);
  38. }
  39.  
  40. inline void rf(){
  41.     ios_base::sync_with_stdio(false);
  42.     cin.tie(nullptr); cout.tie(nullptr);
  43.     if(fopen(file".inp","r")){
  44.         freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
  45.     }
  46. }
  47.  
  48. template<typename T> inline void add(T &x, const T &y)
  49. {
  50.     x+=y;
  51.     if(x>=mod) x-=mod;
  52.     if(x<0) x+=mod;
  53. }
  54.  
  55. template<typename T> inline bool maxi(T &a, T b)
  56. {
  57.     if(a>=b) return 0;
  58.     a=b; return 1;
  59. }
  60.  
  61. template<typename T> inline bool mini(T &a, T b)
  62. {
  63.     if(a<=b) return 0;
  64.     a=b; return 1;
  65. }
  66.  
  67.  
  68. int main() {
  69.     rf();
  70.  
  71.     int n;
  72.     if (!(cin >> n)) return 0;
  73.     vector<int> a(n);
  74.     for (int i = 0; i < n; ++i) cin >> a[i];
  75.  
  76.     const int MAXV = 200;
  77.     uint64_t base = chrono::high_resolution_clock::now().time_since_epoch().count();
  78.     base ^= 0x9e3779b97f4a7c15ULL;
  79.     base |= 1ULL;
  80.  
  81.     vector<uint64_t> powB(n + 1);
  82.     powB[0] = 1;
  83.     for (int i = 1; i <= n; ++i) powB[i] = powB[i - 1] * base;
  84.  
  85.     auto build = [&](const vector<uint64_t>& v) {
  86.         vector<uint64_t> pref(v.size() + 1);
  87.         for (size_t i = 0; i < v.size(); ++i) pref[i + 1] = pref[i] * base + (v[i] + 1);
  88.         return pref;
  89.     };
  90.     auto subhash = [&](const vector<uint64_t>& pref, int l, int len) {
  91.         return pref[l + len] - pref[l] * powB[len];
  92.     };
  93.  
  94.     vector<long long> G(MAXV + 1), H(MAXV + 1);
  95.  
  96.     for (int d = 1; d <= MAXV; ++d) {
  97.         vector<uint64_t> L(n), R(n);
  98.         for (int i = 0; i < n; ++i) {
  99.             int m = a[i] % d;
  100.             L[i] = m;
  101.             R[i] = (d - m) % d;
  102.         }
  103.         vector<uint64_t> Lrev = L;
  104.         reverse(Lrev.begin(), Lrev.end());
  105.         auto prefL = build(Lrev);
  106.         auto prefR = build(R);
  107.  
  108.         long long gsum = 0;
  109.         for (int i = 0; i < n - 1; ++i) {
  110.             int tMax = min(i + 1, n - (i + 1));
  111.             int revStart = n - 1 - i;
  112.             int lo = 0, hi = tMax;
  113.             while (lo < hi) {
  114.                 int mid = (lo + hi + 1) >> 1;
  115.                 if (subhash(prefL, revStart, mid) == subhash(prefR, i + 1, mid)) lo = mid;
  116.                 else hi = mid - 1;
  117.             }
  118.             gsum += lo;
  119.         }
  120.         G[d] = gsum;
  121.     }
  122.  
  123.     long long ans = 0;
  124.     for (int g = MAXV; g >= 1; --g) {
  125.         long long cnt = G[g];
  126.         for (int m = g * 2; m <= MAXV; m += g) cnt -= H[m];
  127.         H[g] = cnt;
  128.         ans += 1LL * g * H[g];
  129.     }
  130.  
  131.     cout << ans << '\n';
  132.     return 0;
  133. }
  134.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin 
5
1 2 3 4 5
stdout 
36
https://ideone.com/qYaLgU
language:
C++14 (gcc 8.3)
created:
17 days ago
visibility:
public

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!