import sys
input = sys.stdin.readline
def f1(x, y):
if x < 0 or y < 0:
return 0
else:
return d[x][y]
def f2(x, y):
if x < 0 or y < 0:
return 0
else:
return d[min(x, n-1)][min(y, m-1)]
q = [0]*2502
i = 2
while i <= 2501:
if q[i] == 0:
for j in range(i+i, 2501, i):
if q[j] == 0:
q[j] = 1
i += 1
n, m = map(int, input().split())
g = [list(map(int, list(input()[:-1]))) for _ in range(n)]
d = [[0]*m for i in range(n)]
d[0][0] = g[0][0]
for i in range(n):
for j in range(m):
d[i][j] = f1(i-1, j) + f1(i, j-1) - f1(i-1, j-1) + g[i][j]
c = 100000000
for k in range(2, max(n, m)+1):
if q[k] == 0:
s = 0
x = k*k
for i in range(k-1, n+k-1, k):
for j in range(k-1, m+k-1, k):
c1 = f2(i, j) - f2(i-k, j) - f2(i, j-k) + f2(i-k, j-k)
s += min(c1, x-c1)
c = min(s, c)
print(c)/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int getFlips(vector<vector<char>> &v,int r,int c,int k)
{
vector<int> arr(2,0);
for(int p = r;p<r+k;p++)
{
for(int q = c;q<c+k;q++)
{
if(p>=v.size() || q>=v[0].size()) arr[0]++;
else arr[(int)(v[p][q]-'0')]++;
}
}
return min(arr[0],arr[1]);
}
int sol(vector<vector<char>> &v,int n,int m,int k){
int sm = 0;
for(int i = 0;i<n;i+=k){
for(int j = 0;j<m;j+=k){
sm+=getFlips(v,i,j,k);
}
}
return sm;
// O(nm)
// 2500 * 2500 = 6250000
}
int main()
{
int n,m;
cin>>n>>m;
vector<vector<char>> v(n,vector<char>(m,'0'));
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
cin>>v[i][j];
}
}
int minV = INT_MAX;
for(int k = 2;k<=20;k++)
minV = min(minV,sol(v,n,m,k));
cout<<minV<<endl;
return 0;
}
181A - Series of Crimes | 1638A - Reverse |
1654C - Alice and the Cake | 369A - Valera and Plates |
1626A - Equidistant Letters | 977D - Divide by three multiply by two |
1654B - Prefix Removals | 1654A - Maximum Cake Tastiness |
1649A - Game | 139A - Petr and Book |
1612A - Distance | 520A - Pangram |
124A - The number of positions | 1041A - Heist |
901A - Hashing Trees | 1283A - Minutes Before the New Year |
1654D - Potion Brewing Class | 1107B - Digital root |
25A - IQ test | 785A - Anton and Polyhedrons |
1542B - Plus and Multiply | 306A - Candies |
1651C - Fault-tolerant Network | 870A - Search for Pretty Integers |
1174A - Ehab Fails to Be Thanos | 1169A - Circle Metro |
780C - Andryusha and Colored Balloons | 1153A - Serval and Bus |
1487C - Minimum Ties | 1136A - Nastya Is Reading a Book |