fork download
  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
stdin
abcdabcd
abcdabcdabcdabcd
stdout
511712897 check
-488287110 check
511712897 check
511712897 check
1