fork download
copy 
  1. #include"bits/stdc++.h" 
  2. using namespace std; 
  3. int main(void) {
  4.     cin.tie(nullptr)->sync_with_stdio(false);
  5.     string s; 
  6.     cin>>s; 
  7.     s = " " + s; 
  8.     vector<int> prefix(s.length(), 0); 
  9.     for(int i = 1; i <= s.length()-1; ++i) {
  10.         prefix[i] = prefix[i-1] + int(s[i] - '0');  
  11.         prefix[i] %= 3; 
  12.     }
  13.     vector<int> pos[3]; 
  14.     pos[0].push_back(0);   
  15.     long long ans = 0; 
  16.     int num = 0; 
  17.     for(int j = 1; j <= s.length()-1; ++j) {
  18.         int digit = s[j] - '0'; 
  19.         num = num * 10 + digit; 
  20.         num %= 97; 
  21.         if(num == 0) {
  22.             int need = prefix[j]; 
  23.             int cnt = lower_bound(pos[need].begin(), pos[need].end(), j) - pos[need].begin();  
  24.             ans += cnt; 
  25.         }
  26.         pos[prefix[j]].push_back(j); 
  27.     }
  28.     cout<<ans; 
  29. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0Xr649
language:
C++ (gcc 8.3)
created:
4 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!