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;
- int nfac[N];
- int r, c, ip[N][N], g[N][N], C[N][N], a[N][N];
- ll gcd(ll a, ll b) {
- if (b == 0) return a;
- return gcd(b, a%b);
- }
- 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) {
- int g = 0;
- 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);
- g = gcd(g, ip[ti][tj]);
- }
- 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;
- }
- }
- int allg = 0;
- for (int i = 1; i <= p; ++i)
- for (int j = 1; j <= q; ++j)
- allg = gcd(allg, a[i][j]);
- return nfac[allg];
- }
- void main2() {
- for (int i = 1; i <= r; ++i)
- for (int j = 1; j <= c; ++j) {
- scanf("%d", ip[i] + j);
- }
- 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)
- ans += chk(i, j);
- printf("%lld\n", ans);
- }
- void build() {
- 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