Advertisement
Guest User

Untitled

a guest
Oct 20th, 2019
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.64 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.  
  9. int nfac[N];
  10. int r, c, ip[N][N], g[N][N], C[N][N], a[N][N];
  11.  
  12. ll gcd(ll a, ll b) {
  13. if (b == 0) return a;
  14. return gcd(b, a%b);
  15. }
  16.  
  17. ll chk(int p, int q) {
  18. if (p * q == 1 || p * q == (r * c)) return 0;
  19.  
  20. for (int i = 1; i <= r; ++i) {
  21. for (int j = 1; j <= c; ++j) {
  22. g[i][j] = 0;
  23. C[i][j] = ip[i][j];
  24. }
  25. }
  26. int n = r / p;
  27. int m = c / q;
  28.  
  29. for (int i = 1; i <= p; ++i)
  30. for (int j = 1; j <= q; ++j) {
  31. int g = 0;
  32. for (int ii = 1; ii <= n; ++ii)
  33. for (int jj = 1; jj <= m; ++jj) {
  34. int ti = ii + n * (i - 1);
  35. int tj = jj + m * (j - 1);
  36. g = gcd(g, ip[ti][tj]);
  37. }
  38. a[i][j] = g;
  39. }
  40.  
  41. for (int i = 1; i <= p; ++i)
  42. for (int j = 1; j <= q; ++j) {
  43. for (int ii = 1; ii <= n; ++ii)
  44. for (int jj = 1; jj <= m; ++jj) {
  45. int ti = ii + n * (i - 1);
  46. int tj = jj + m * (j - 1);
  47. if (ip[ti][tj] / a[i][j] != ip[ii][jj] / a[1][1]) return 0;
  48. }
  49. }
  50. int allg = 0;
  51. for (int i = 1; i <= p; ++i)
  52. for (int j = 1; j <= q; ++j)
  53. allg = gcd(allg, a[i][j]);
  54.  
  55. return nfac[allg];
  56. }
  57.  
  58. void main2() {
  59. for (int i = 1; i <= r; ++i)
  60. for (int j = 1; j <= c; ++j) {
  61. scanf("%d", ip[i] + j);
  62. }
  63. ll ans = 0;
  64. for (int i = 1; i <= r; ++i) if (r % i == 0)
  65. for (int j = 1; j <= c; ++j) if (c % j == 0)
  66. ans += chk(i, j);
  67.  
  68. printf("%lld\n", ans);
  69. }
  70.  
  71. void build() {
  72. for (int i = 1; i < X; ++i) {
  73. nfac[i]++;
  74. for (int j = i+i; j < X; j += i) nfac[j]++;
  75. }
  76. }
  77.  
  78. int main() {
  79. build();
  80. while (scanf("%d%d", &r, &c)) {
  81. if (r == 0) break;
  82. main2();
  83. }
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement