Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int X = 77777;
- const int N = 555;
- const int LG = 10;
- int nfac[X], lg[N];
- int r, c, ip[N][N], g[N][N], C[N][N], a[N][N];
- int sp[LG][N][N];
- int gcd(int a, int b) {
- if (b == 0) return a;
- return gcd(b, a%b);
- }
- inline int agcd(int i, int j, int ii, int jj) {
- ll res = 0;
- int bt = lg[(jj - j + 1)];
- for (int t = i; t <= ii; ++t) {
- int nb = jj - (1 << bt) + 1;
- ll tg = gcd(sp[bt][t][j], sp[bt][t][nb]);
- res = gcd(res, tg);
- }
- return res;
- }
- int chk(int p, int q) {
- if (p * q == 1 || p * q == (r * c)) return 0;
- int n = r / p;
- int m = c / q;
- for (int i = 1; i <= p; ++i)
- for (int j = 1; j <= q; ++j) {
- int g = agcd(n * (i-1) + 1, m * (j-1) + 1, n * i, m * j);
- a[i][j] = g;
- }
- for (int i = 1; i <= r; ++i)
- for (int j = 1; j <= c; ++j) {
- int i1 = (i + n - 1) / n, i2 = (i - 1) % n + 1;
- int j1 = (j + m - 1) / m, j2 = (j - 1) % m + 1;
- if (ip[i][j] * a[1][1] != ip[i2][j2] * a[i1][j1])
- return 0;
- }
- // for (int i = 1; i <= p; ++i)
- // for (int j = 1; j <= q; ++j) {
- // for (int ii = 1; ii <= n; ++ii)
- // for (int jj = 1; jj <= m; ++jj) {
- // int ti = ii + n * (i - 1);
- // int tj = jj + m * (j - 1);
- // if (ip[ti][tj] / a[i][j] != ip[ii][jj] / a[1][1]) return 0;
- // }
- // }
- return 1;
- }
- void main2() {
- for (int i = 1; i <= r; ++i)
- for (int j = 1; j <= c; ++j) {
- //ip[i][j] = 65536;
- scanf("%d", ip[i] + j);
- }
- for (int i = 1; i <= r; ++i) {
- for (int j = 1; j <= c; ++j)
- sp[0][i][j] = ip[i][j];
- for (int k = 0; k < lg[c]; ++k) {
- for (int j = 1; j <= c; ++j) {
- int nj = min(c, j + (1 << k));
- sp[k+1][i][j] = gcd(sp[k][i][j], sp[k][i][nj]);
- }
- }
- }
- ll ans = 0;
- for (int i = 1; i <= r; ++i) if (r % i == 0) {
- for (int j = 1; j <= c; ++j) if (c % j == 0) {
- if (chk(i, j)) {
- ++ans;
- }
- }
- }
- ll allg = agcd(1, 1, r, c);
- ans *= nfac[allg];
- printf("%lld\n", ans);
- }
- void build() {
- lg[0] = -1;
- for (int i = 1; i < N; ++i) lg[i] = 1 + lg[i / 2];
- for (int i = 1; i < X; ++i) {
- nfac[i]++;
- for (int j = i+i; j < X; j += i) nfac[j]++;
- }
- }
- int main() {
- build();
- while (scanf("%d%d", &r, &c)) {
- if (r == 0) break;
- main2();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement