fork(1) download
copy 
  1. #include <iostream>
  2. #define PB 99991
  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. string s1, s2;
  12.  
  13. int main() 
  14. {
  15.     ppow[0] = 1;
  16.     for (int i = 1; i < MAX+1; ++i)
  17.         ppow[i] = (ppow[i-1] * PB) % MOD;
  18.     cin >> s1; cin >> s2;
  19. 	int l1 = s1.size(), l2 = s2.size();
  20.     h1[0] = s1[0];
  21.     //cout << h1[0] << " ";
  22.     for (int i = 1; i < l1; ++i)
  23.     {
  24.         h1[i] = (((h1[i-1] * PB) % MOD) + s1[i]) % MOD;
  25.         //cout << h1[i] << " " ;
  26.     }
  27.     //cout << '\n'; 
  28.     h2[0] = s2[0];
  29.     //cout << h2[0] << " ";
  30.     for (int i = 1; i < l2; ++i)
  31.     {
  32.         h2[i] = (((h2[i-1] * PB) % MOD) + s2[i]) % MOD;
  33.         //cout << h2[i] << " " ;
  34.     }
  35.     //cout << '\n'; 
  36.     int ans = 0;
  37.     for (int i = 1; i <= l1; ++i)
  38.     {
  39.         if (l1 % i == 0 && l2 % i == 0)
  40.         {
  41.             bool flag = true;
  42.             ll temp = h1[i-1];
  43.             for (int j = 0; j < l1; j = j + i)
  44. 			{
  45. 				if (!j)
  46. 				{
  47. 					if (temp != h1[j+i-1])
  48. 						flag = false;
  49.  
  50. 				}	
  51.                 else if (temp != (h1[j+i-1] - ((h1[j-1] * ppow[i]) % MOD)))
  52.                     flag = false;		
  53. 			}		
  54.             for (int j = 0; j < l2; j = j + i)
  55.             {
  56. 				if (i == 4)
  57. 					cout << (h2[j+i-1] - ((h2[j-1] * ppow[i]) % MOD)) << " " << "check" << '\n';
  58. 				if (!j)
  59. 				{
  60. 					if (temp != h2[j+i-1])
  61. 						flag = false;
  62. 				}	
  63.                 else if (temp != (h2[j+i-1] - ((h2[j-1] * ppow[i]) % MOD)))
  64.                     flag = false;
  65.             }
  66.             ans += flag;
  67.         }
  68.     }
  69.     cout << ans;
  70.     return 0;
  71. }
Success #stdin #stdout 0s 5824KB
comments (?)
stdin
copy 
abcdabcd
abcdabcdabcdabcd
stdout
copy 
511712897 check
-488287110 check
511712897 check
511712897 check
1
https://ideone.com/HWtRxk
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!