#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
const ll inf=1e18+18ll;
#define pb push_back
ll n,k;
ll a[N];
/*
void build(int v,int tl,int tr){
if(tl==tr)t[v]=a[tl],return;
int tm=(tl+tr)/2;
build(v+v,tl,tm);
build(v+v+1,tm+1,tr);
t[v]=min(t[v+v],t[v+v+1]);
}
void pushdown(int v){
if(lazy[v]==0)return;
t[v+v]-=lazy[v];
t[v+v+1]-=lazy[v];
lazy[v+v]+=lazy[v];
lazy[v+v+1]+=lazy[v];
lazy[v]=0;
}
void update(int v,int tl,int tr,int l,int r,ll d){
if(l>r)return;
if(tl>=l&&tr<=r){
lazy[v]+=d;
t[v]-=d;
return;
}
pushdown(v);
int tm=(tl+tr)/2;
if(l<=tm)update(v+v,tl,tm,l,r,d);
if(r>tm)update(v+v+1,tm+1,tr,l,r,d);
t[v]=min(t[v+v],t[v+v+1]);
}
ll query(int v,int tl,int tr,int l,int r){
if(tl>=l&&tr<=r)return t[v];
ll res=inf;
int tm=(tl+tr)/2;
pushdown(v);
if(l<=tm)res=min(res,query(v+v,tl,tm,l,r));
if(r>tm)res=min(res,query(v+v+1,tm+1,tr,l,r));
return res;
}*/
vector<int> J[N];
int main(){
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
int n;
cin>>n>>k;
if(k==0){
cout<<(n*1ll*n/2ll)<<'\n';
return 0;
}
for(int i=0;i<k;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
J[y1].push_back(n-x1+1);
}
vector<int> div;div.push_back(1);
for(int i=2;i*i<=n;i++){
if(n%i==0){
div.push_back(i);
if(n/i!=i)div.push_back(n/i);
}
}
sort(div.begin(),div.end());
ll answ=n*1ll*n;
for(int i=0;i<div.size();i++){
ll tmp=0ll;
//cerr<<div[i]<<' ';
ll x=n/div[i];
if(x%2){ll y=x/2+1,z=x/2;tmp=y*y+z*z;}
else{ll y=x/2;tmp=y*y+y*y;}
tmp=tmp*1ll*div[i]*1ll*div[i];//cerr<<tmp<<' ';
for(int j=1;j<=n;j++){//cerr<<tmp<<' ';
for(int p=0;p<=J[j].size();p++){
if(j%div[i]==0){
if((j/div[i])%2){
if(J[j][p]%div[i]==0){
if((J[j][p]/div[i])%2){
tmp--;
}
}else if((J[j][p]/div[i])%2==0){
tmp--;
}
}
}else if((j/div[i])%2==0){
if(J[j][p]%div[i]==0){
if((J[j][p]/div[i])%2){
tmp--;
}
}else if((J[j][p]/div[i])%2==0){
tmp--;
}
}else if((j/div[i])%2==1){
if(J[j][p]%div[i]==0){
if((J[j][p]/div[i])%2==0){
tmp--;
}
}else if((J[j][p]/div[i])%2==1){
tmp--;
}
}
}//cerr<<tmp<<' ';
}
answ=min(answ,min(tmp,n*1ll*n-tmp));
//cerr<<answ<<'\n';
}
cout<<answ<<'\n';
}
Compilation message
chessboard.cpp: In function 'int main()':
chessboard.cpp:80:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<div.size();i++){
~^~~~~~~~~~~
chessboard.cpp:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int p=0;p<=J[j].size();p++){
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
144 ms |
9276 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
5112 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
5112 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
144 ms |
9276 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
