fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MAX_N 1000000
  5.  
  6. int gcd(int a, int b){
  7. 	while(b){
  8. 		int r = a%b;
  9. 		a = b;
  10. 		b = r;
  11. 	}
  12. 	return a;
  13. }
  14.  
  15. int main() {
  16.     int N;
  17.     char S[MAX_N];
  18.     scanf("%d %s", &N, S+1);
  19.  
  20.     int ans = 0;
  21.     for(int i=1; i<=N; i++){
  22.         if(S[i]=='b') continue;
  23.         char last = S[i]=='a' ? 'c' : 'a';
  24.  
  25.         for(int q=1; q*q<=i; q++){
  26.             if(i%(q*q)!=0) continue;
  27.  
  28.             for(int p=q+1; ; p++){
  29.  
  30.                 int j = i*p/q;
  31.                 int k = j*p/q;
  32.  
  33.                 if(k>N)
  34.                     break;
  35.                 if(S[j]=='b' && S[k]==last && gcd(p, q)==1)
  36.                     ans++;
  37.             }
  38.         }
  39.     }
  40.  
  41.     printf("%d\n", ans);
  42.  
  43.     return 0;
  44. }
  45.  
Success #stdin #stdout 0s 16096KB
comments (?)
stdin
copy 
15
ccaccbbbaccccca
stdout
copy 
2
https://ideone.com/Xxg6Ut
language:
C++14 (gcc 8.3)
created:
6 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!