Advertisement
Guest User

Untitled

a guest
Oct 20th, 2019
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.33 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. ll gcd(ll a, ll b) {
  15. if (b == 0) return a;
  16. return gcd(b, a%b);
  17. }
  18.  
  19. inline ll 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. ll chk(int p, int q) {
  31. if (p * q == 1 || p * q == (r * c)) return 0;
  32.  
  33. for (int i = 1; i <= r; ++i) {
  34. for (int j = 1; j <= c; ++j) {
  35. g[i][j] = 0;
  36. C[i][j] = ip[i][j];
  37. }
  38. }
  39. int n = r / p;
  40. int m = c / q;
  41.  
  42. for (int i = 1; i <= p; ++i)
  43. for (int j = 1; j <= q; ++j) {
  44. ll g = agcd(n * (i-1) + 1, m * (j-1) + 1, n * i, m * j);
  45. a[i][j] = g;
  46. }
  47.  
  48. for (int i = 1; i <= p; ++i)
  49. for (int j = 1; j <= q; ++j) {
  50. for (int ii = 1; ii <= n; ++ii)
  51. for (int jj = 1; jj <= m; ++jj) {
  52. int ti = ii + n * (i - 1);
  53. int tj = jj + m * (j - 1);
  54. if (ip[ti][tj] / a[i][j] != ip[ii][jj] / a[1][1]) return 0;
  55. }
  56. }
  57. return 1;
  58. }
  59.  
  60. void main2() {
  61. for (int i = 1; i <= r; ++i)
  62. for (int j = 1; j <= c; ++j) {
  63. scanf("%d", ip[i] + j);
  64. }
  65.  
  66. for (int i = 1; i <= r; ++i) {
  67. for (int j = 1; j <= c; ++j)
  68. sp[0][i][j] = ip[i][j];
  69. for (int k = 0; k < LG - 1; ++k) {
  70. for (int j = 1; j <= c; ++j) {
  71. int nj = min(c, j + (1 << k));
  72. sp[k+1][i][j] = gcd(sp[k][i][j], sp[k][i][nj]);
  73. }
  74. }
  75. }
  76.  
  77. int minp = r;
  78. int minq = c;
  79.  
  80. for (int i = 1; i <= r; ++i) if (r % i == 0) {
  81. if (chk(i, c)) {
  82. minp = i;
  83. break;
  84. }
  85. }
  86. for (int i = 1; i <= c; ++i) if (c % i == 0) {
  87. if (chk(r, i)) {
  88. minq = i;
  89. break;
  90. }
  91. }
  92.  
  93. ll ans = 0;
  94.  
  95. int nr = r / minp;
  96. int nc = c / minq;
  97.  
  98. ans = nfac[nr] * nfac[nc] - 1;
  99. if (nr > 1 || nc > 1) --ans;
  100.  
  101. //printf("%d %d\n", nr, nc);
  102.  
  103. ll allg = agcd(1, 1, r, c);
  104. ans *= nfac[allg];
  105.  
  106. printf("%lld\n", ans);
  107. }
  108.  
  109. void build() {
  110. lg[0] = -1;
  111. for (int i = 1; i < N; ++i) lg[i] = 1 + lg[i / 2];
  112.  
  113. for (int i = 1; i < X; ++i) {
  114. nfac[i]++;
  115. for (int j = i+i; j < X; j += i) nfac[j]++;
  116. }
  117. }
  118.  
  119. int main() {
  120. build();
  121. while (scanf("%d%d", &r, &c)) {
  122. if (r == 0) break;
  123. main2();
  124. }
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement