Advertisement
Guest User

Untitled

a guest
Oct 20th, 2019
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.28 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. const int X = 77777;
  7. const int N = 555;
  8. const int LG = 10;
  9.  
  10. int nfac[X], lg[N];
  11. int r, c, ip[N][N], g[N][N], C[N][N], a[N][N];
  12. int sp[LG][N][N];
  13.  
  14. int gcd(int a, int b) {
  15. if (b == 0) return a;
  16. return gcd(b, a%b);
  17. }
  18.  
  19. inline int agcd(int i, int j, int ii, int jj) {
  20. ll res = 0;
  21. int bt = lg[(jj - j + 1)];
  22. for (int t = i; t <= ii; ++t) {
  23. int nb = jj - (1 << bt) + 1;
  24. ll tg = gcd(sp[bt][t][j], sp[bt][t][nb]);
  25. res = gcd(res, tg);
  26. }
  27. return res;
  28. }
  29.  
  30. int chk(int p, int q) {
  31. if (p * q == 1 || p * q == (r * c)) return 0;
  32.  
  33. int n = r / p;
  34. int m = c / q;
  35.  
  36. for (int i = 1; i <= p; ++i)
  37. for (int j = 1; j <= q; ++j) {
  38. int g = agcd(n * (i-1) + 1, m * (j-1) + 1, n * i, m * j);
  39. a[i][j] = g;
  40. }
  41. for (int i = 1; i <= r; ++i)
  42. for (int j = 1; j <= c; ++j) {
  43. int i1 = (i + n - 1) / n, i2 = (i - 1) % n + 1;
  44. int j1 = (j + m - 1) / m, j2 = (j - 1) % m + 1;
  45. if (ip[i][j] * a[1][1] != ip[i2][j2] * a[i1][j1])
  46. return 0;
  47. }
  48.  
  49. // for (int i = 1; i <= p; ++i)
  50. // for (int j = 1; j <= q; ++j) {
  51. // for (int ii = 1; ii <= n; ++ii)
  52. // for (int jj = 1; jj <= m; ++jj) {
  53. // int ti = ii + n * (i - 1);
  54. // int tj = jj + m * (j - 1);
  55. // if (ip[ti][tj] / a[i][j] != ip[ii][jj] / a[1][1]) return 0;
  56. // }
  57. // }
  58. return 1;
  59. }
  60.  
  61. void main2() {
  62. for (int i = 1; i <= r; ++i)
  63. for (int j = 1; j <= c; ++j) {
  64. //ip[i][j] = 65536;
  65. scanf("%d", ip[i] + j);
  66. }
  67.  
  68. for (int i = 1; i <= r; ++i) {
  69. for (int j = 1; j <= c; ++j)
  70. sp[0][i][j] = ip[i][j];
  71. for (int k = 0; k < lg[c]; ++k) {
  72. for (int j = 1; j <= c; ++j) {
  73. int nj = min(c, j + (1 << k));
  74. sp[k+1][i][j] = gcd(sp[k][i][j], sp[k][i][nj]);
  75. }
  76. }
  77. }
  78.  
  79. ll ans = 0;
  80.  
  81. for (int i = 1; i <= r; ++i) if (r % i == 0) {
  82. for (int j = 1; j <= c; ++j) if (c % j == 0) {
  83. if (chk(i, j)) {
  84. ++ans;
  85. }
  86. }
  87. }
  88.  
  89. ll allg = agcd(1, 1, r, c);
  90. ans *= nfac[allg];
  91.  
  92. printf("%lld\n", ans);
  93. }
  94.  
  95. void build() {
  96. lg[0] = -1;
  97. for (int i = 1; i < N; ++i) lg[i] = 1 + lg[i / 2];
  98.  
  99. for (int i = 1; i < X; ++i) {
  100. nfac[i]++;
  101. for (int j = i+i; j < X; j += i) nfac[j]++;
  102. }
  103. }
  104.  
  105. int main() {
  106. build();
  107. while (scanf("%d%d", &r, &c)) {
  108. if (r == 0) break;
  109. main2();
  110. }
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement