fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef unsigned long long ull;
  8.  
  9. // Sử dụng Modulo 2^61 - 1 (Số nguyên tố Mersenne) cực nhanh và an toàn
  10. typedef __int128_t int128;
  11. const ull MOD = (1ULL << 61) - 1;
  12.  
  13. ull modMul(ull a, ull b) {
  14.     int128 res = (int128)a * b;
  15.     ull ans = (ull)(res >> 61) + (ull)(res & MOD);
  16.     if (ans >= MOD) ans -= MOD;
  17.     return ans;
  18. }
  19.  
  20. int N;
  21. int A[100005];
  22. ull powB[100005];
  23. ull hFwd[100005], hBwd[100005];
  24. int B[100005], revC[100005];
  25. long long F[205], exact[205];
  26.  
  27. void buildHash(int* v, ull* h) {
  28.     h[0] = 0;
  29.     for (int i = 0; i < N; i++) {
  30.         h[i + 1] = (modMul(h[i], 211) + v[i]) % MOD;
  31.     }
  32. }
  33.  
  34. ull getHash(ull* h, int l, int r) {
  35.     ull res = h[r] + MOD - modMul(h[l - 1], powB[r - l + 1]);
  36.     return res % MOD;
  37. }
  38.  
  39. int main() {
  40.     // Tăng tốc nhập xuất tối đa
  41.     ios::sync_with_stdio(false);
  42.     cin.tie(NULL);
  43.  
  44.     if (!(cin >> N)) return 0;
  45.     for (int i = 1; i <= N; i++) cin >> A[i];
  46.  
  47.     powB[0] = 1;
  48.     for (int i = 1; i <= N; i++) powB[i] = modMul(powB[i - 1], 211);
  49.  
  50.     for (int g = 1; g <= 200; g++) {
  51.         // Tối ưu: Điền trực tiếp vào mảng tĩnh
  52.         for (int i = 0; i < N; i++) {
  53.             int val = A[i + 1] % g;
  54.             B[i] = val;
  55.             revC[N - 1 - i] = (val == 0) ? 0 : g - val;
  56.         }
  57.  
  58.         buildHash(B, hFwd);
  59.         buildHash(revC, hBwd);
  60.  
  61.         long long total_g = 0;
  62.         for (int i = 1; i < N; i++) {
  63.             int low = 1, high = min(i, N - i);
  64.             int best_k = 0;
  65.  
  66.             // Một tối ưu nhỏ: check nhanh k=1 trước khi vào Binary Search
  67.             if ( (A[i] + A[i+1]) % g != 0 ) continue;
  68.  
  69.             while (low <= high) {
  70.                 int mid = low + (high - low) / 2;
  71.                 // So sánh hash
  72.                 if (getHash(hFwd, i - mid + 1, i) == getHash(hBwd, N - (i + mid) + 1, N - i)) {
  73.                     best_k = mid;
  74.                     low = mid + 1;
  75.                 } else {
  76.                     high = mid - 1;
  77.                 }
  78.             }
  79.             total_g += best_k;
  80.         }
  81.         F[g] = total_g;
  82.     }
  83.  
  84.     long long total_ans = 0;
  85.     for (int g = 200; g >= 1; g--) {
  86.         exact[g] = F[g];
  87.         for (int m = 2 * g; m <= 200; m += g) exact[g] -= exact[m];
  88.         total_ans += (long long)g * exact[g];
  89.     }
  90.  
  91.     cout << total_ans << endl;
  92.     return 0;
  93. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/94D6Hi
language:
C++14 (gcc 8.3)
created:
22 hours 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!