#include <iostream>
#include <stdio.h>
using namespace std;
const int MAXK=100005;
long long mini[MAXK], maxi[MAXK], minj[MAXK], maxj[MAXK];
long long NumWhite(long long, long long, long long, long long, long long cellLen);
long long FindAns(long long n, int k, int cellLen);
int main()
{
long long n, k;
cin>>n>>k;
for (int i=0; i<k; i++)
scanf("%d%d%d%d", mini+i, minj+i, maxi+i, maxj+i);
long long ans=n*n;
for (int cellLen=1; cellLen*cellLen<=n; cellLen++)
if (n%cellLen==0)
{
ans=min(ans, FindAns(n, k, cellLen));
ans=min(ans, FindAns(n, k, n/cellLen));
}
cout<<ans<<'\n';
char I;
cin >> I;
return 0;
}
long long FindAns(long long n, long long k, long long cellLen)
{
if (cellLen>=n) return n*n;
long long shouldWhite=0, shouldBlack=0, isBlack=0;
for (int i=0; i<k; i++)
{
shouldWhite+=NumWhite(mini[i], minj[i], maxi[i], maxj[i], cellLen);
isBlack+=(maxi[i]-mini[i]+1)*(maxj[i]-minj[i]+1);
}
shouldBlack=(n*n-NumWhite(1, 1, n, n, cellLen))-(isBlack-shouldWhite);
return min(shouldWhite+shouldBlack, n*n-(shouldWhite+shouldBlack));
}
long long NumWhite(long long mini, long long minj, long long maxi, long long maxj, long long len)
{
if (!mini) mini=1;
if (!minj) minj=1;
if (mini==1 && minj==1)
{
long long ans=0, i=maxi, j=maxj;
ans+=len*len*(((i/len)*(j/len)+1)/2);
if ((i/len)%2)
ans+=(i%len)*((j/len)/2)*len;
else
ans+=(i%len)*((j/len+1)/2)*len;
if ((j/len)%2)
ans+=(j%len)*((i/len)/2)*len;
else
ans+=(j%len)*((i/len+1)/2)*len;
if ((i/len)%2==(j/len)%2)
ans+=(i%len)*(j%len);
return ans;
}
return NumWhite(1, 1, maxi, maxj, len)-
NumWhite(1, 1, maxi, minj-1, len)-NumWhite(1, 1, mini-1, maxj, len)+
NumWhite(1, 1, mini-1, minj-1, len);
}
Compilation message
chessboard.cpp: In function 'int main()':
chessboard.cpp:15:51: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
scanf("%d%d%d%d", mini+i, minj+i, maxi+i, maxj+i);
~~~~~~ ^
chessboard.cpp:15:51: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
chessboard.cpp:15:51: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
chessboard.cpp:15:51: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'long long int*' [-Wformat=]
chessboard.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", mini+i, minj+i, maxi+i, maxj+i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/cc23stgX.o: In function `main':
chessboard.cpp:(.text.startup+0xc5): undefined reference to `FindAns(long long, int, int)'
chessboard.cpp:(.text.startup+0xe0): undefined reference to `FindAns(long long, int, int)'
collect2: error: ld returned 1 exit status
