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];
- ll gcd(ll a, ll b) {
- if (b == 0) return a;
- return gcd(b, a%b);
- }
- inline ll 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;
- }
- ll chk(int p, int q) {
- if (p * q == 1 || p * q == (r * c)) return 0;
- for (int i = 1; i <= r; ++i) {
- for (int j = 1; j <= c; ++j) {
- g[i][j] = 0;
- C[i][j] = ip[i][j];
- }
- }
- int n = r / p;
- int m = c / q;
- for (int i = 1; i <= p; ++i)
- for (int j = 1; j <= q; ++j) {
- ll g = agcd(n * (i-1) + 1, m * (j-1) + 1, n * i, m * j);
- a[i][j] = g;
- }
- 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) {
- 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 - 1; ++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]);
- }
- }
- }
- int minp = r;
- int minq = c;
- for (int i = 1; i <= r; ++i) if (r % i == 0) {
- if (chk(i, c)) {
- minp = i;
- break;
- }
- }
- for (int i = 1; i <= c; ++i) if (c % i == 0) {
- if (chk(r, i)) {
- minq = i;
- break;
- }
- }
- ll ans = 0;
- int nr = r / minp;
- int nc = c / minq;
- ans = nfac[nr] * nfac[nc] - 1;
- if (nr > 1 || nc > 1) --ans;
- //printf("%d %d\n", nr, nc);
- 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