fork download
copy 
  1. #include <iostream>
  2. #define PB 163
  3. #define MOD 1000000007
  4. #define MAX 100000
  5. #define ll long long
  6. using namespace std;
  7.  
  8. ll ppow[MAX+1];
  9. ll h1[MAX+1];
  10. ll h2[MAX+1];
  11.  
  12. int main() 
  13. {
  14.     ppow[0] = 1;
  15.     for (int i = 1; i < MAX+1; ++i)
  16.         ppow[i] = (ppow[i-1] * PB) % MOD;
  17.     string s1, s2;
  18. 	s1.erase(); s2.erase();
  19.     cin >> s1; cin >> s2;
  20.     h1[0] = s1[0] - 'a';
  21.     //cout << h1[0] << " ";
  22.     for (int i = 1; i < s1.size(); ++i)
  23.     {
  24.         h1[i] = (((h1[i-1] * PB) % MOD) + (s1[i] - 'a')) % MOD;
  25.         //cout << h1[i] << " " ;
  26.     }
  27.     //cout << '\n'; 
  28.     h2[0] = s2[0] - 'a';
  29.     //cout << h2[0] << " ";
  30.     for (int i = 1; i < s2.size(); ++i)
  31.     {
  32.         h2[i] = (((h2[i-1] * PB) % MOD) + (s2[i] - 'a')) % MOD;
  33.         //cout << h2[i] << " " ;
  34.     }
  35.     //cout << '\n'; 
  36.     int ans = 0;
  37.     int l1 = s1.size(), l2 = s2.size();
  38.     for (int i = 1; i <= l1; ++i)
  39.     {
  40.         if (l1 % i == 0 && l2 % i == 0)
  41.         {
  42.             bool flag = true;
  43.             ll temp = h1[i-1];
  44.             for (int j = 0; j < l1; j = j + i)
  45.                 if (temp != (h1[j+i-1] - ((h1[j-1] * ppow[i]) % MOD)))
  46.                     flag = false;
  47.             for (int j = 0; j < l2; j = j + i)
  48.             {
  49.                 //if (i == 4)
  50.                 //  cout << (h2[j+i-1] - ((h2[j-1] * ppow[i]) % MOD)) << "check" << '\n';
  51.                 if (temp != (h2[j+i-1] - ((h2[j-1] * ppow[i]) % MOD)))
  52.                     flag = false;
  53.             }
  54.             ans += flag;
  55.         }
  56.     }
  57.     cout << ans << '\n';
  58.     return 0;
  59. }
Success #stdin #stdout 0s 5780KB
comments (?)
stdin
copy 
abcdabcd
abcdabcdabcdabcd
stdout
copy 
2
https://ideone.com/1cv777
language:
C++ (gcc 8.3)
created:
10 years 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!