#include <bits/stdc++.h>
//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define endl '\n'
//#define int long long
using namespace std;
//using namespace __gnu_pbds;
//template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 1e5 + 100;
const int M = 21890;
const ll mod = 1e9 + 7;
const ll MOD = 998244353;
const int P = 1336;
const ld eps = 0.000000001;
const int inf = 1e9 + 7;
const ll inff = 1e18 + 7;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
int l1[N], r1[N], l2[N], r2[N];
int m;
int lp[N];
vector <int> pr;
vector < pair <int, int> > ve;
vector <int> a;
void DFS(int i, ll ch)
{
// cerr << i << " " << ch << endl;
if (i == ve.size())
{
a.pb(ch);
return;
}
for(int j = 0; j <= ve[i].S; j++)
{
if (j == 0) DFS(i + 1, ch);
else
{
ch *= ve[i].F;
DFS(i + 1, ch);
}
}
}
pair <int, pair <ll, ll> > get(ll r, ll x, ll y, int fl)
{
ll gx = x / r, gy = y / r;
if (x % r) gx++;
if (y % r) gy++;
bool f;
if (fl == 0)
{
if (gx % 2)
{
if (gy % 2) f = 0;
else f = 1;
}
else if (gy % 2) f = 1;
else f = 0;
}
else
{
if (gx % 2)
{
if (gy % 2) f = 1;
else f = 0;
}
else if (gy % 2) f = 0;
else f = 1;
}
ll bx = 1ll * gx * r - x + 1;
ll by = 1ll * gy * r - y + 1;
return {f, {bx, by}};
}
ll solve(ll r, ll x1, ll y1, ll x2, ll y2, int fl)
{
ll gx1 = x1 / r + 1, gx2 = x2 / r;
if (x1 % r != 1) gx1++;
if (x1 % r == 0) gx1--;
ll gy1 = y1 / r + 1, gy2 = y2 / r;
if (y1 % r != 1) gy1++;
if (y1 % r == 0) gy1--;
if (r == 1)
{
gx1 = x1;
gx2 = x2;
gy1 = y1;
gy2 = y2;
}
if (gx1 > gx2 || gy1 > gy2)
{
// cout << "! " << gx1 << " " << gx2 << " " << gy1 << " " << gy2 << endl;
if (gx1 > gx2 && gy1 > gy2)
{
pair < int, pair <ll, ll> > p = get(r, x1, y1, fl);
// cout << x1 << " " << y1 << " " << p.S.F << " " << p.S.S << endl;
if (x1 + p.S.F > x2 && y1 + p.S.S > y2)
{
// cout << x1 << " " << y1 << " " << p.F << endl;
if (p.F == 0) return 1ll * (x2 - x1 + 1) * (y2 - y1 + 1);
else return 0;
}
if (x1 + p.S.F > x2)
{
ll S = 1ll * (x2 - x1 + 1) * p.S.S;
if (p.F == 0) return S;
else return 1ll * (x2 - x1 + 1) * (y2 - y1 + 1) - S;
}
if (y1 + p.S.S > y2)
{
ll S = 1ll * (y2 - y1 + 1) * p.S.F;
if (p.F == 0) return S;
else return 1ll * (x2 - x1 + 1) * (y2 - y1 + 1) - S;
}
ll v1 = 1ll * p.S.F * p.S.S + 1ll * (x2 - x1 + 1 - p.S.F) * (y2 - y1 + 1 - p.S.S);
ll v2 = 1ll * (x2 - x1 + 1) * (y2 - y1 + 1) - v1;
// cout << "!!! " << v1 << " " << v2 << endl;
if (p.F == 0) return v1;
else return v2;
}
return 0;
}
ll stx = 1ll * gx1 * r - r + 1;
ll ex = 1ll * gx2 * r;
ll sty = 1ll * gy1 * r - r + 1;
ll ey = 1ll * gy2 * r;
ll kolx = (gx2 - gx1 + 1 + 1) / 2;
ll koly = (gy2 - gy1 + 1 + 1) / 2;
ll S = 1ll * kolx * koly * r * r;
kolx = (gx2 - gx1 + 1) / 2;
koly = (gy2 - gy1 + 1) / 2;
S += 1ll * kolx * koly * r * r;
pair < int, pair <ll, ll> > p = get(r, stx, sty, fl);
// cout << p.F << " " << S << endl;
if (p.F == 0) return S;
else return 1ll * (ex - stx + 1) * (ey - sty + 1) - S;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
srand(time(0));
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int n;
cin >> n >> m;
for(int i = 0; i < m; i++)
{
cin >> l1[i] >> r1[i] >> l2[i] >> r2[i];
// cout << solve(2, l1[i], r1[i], l2[i], r2[i], 1) << endl;
}
// cout << get_ans(2, n);
//
// return 0;
for(int i = 2; i < N; i++)
{
if (lp[i] == 0)
{
lp[i] = i;
pr.pb(i);
}
for(int j = 0; j < pr.size() && pr[j] * i < N && pr[j] <= lp[i]; j++)
{
lp[pr[j] * i] = pr[j];
}
}
if (lp[n] == n)
{
cout << get_ans(1, n);
return 0;
}
int ch = n, kopn = n;
while (ch > 1)
{
// cerr << ch << endl;3
int d = lp[ch];
if (ve.size() && ve.back().F == d) ve.back().S++;
else ve.pb({d, 1});
ch /= d;
}
// return 0;
DFS(0, 1);
ll ans = inff;
for(auto to: a)
{
// cout << to << endl;
if (to == kopn) continue;
n = kopn;
int r = to;
ll S = 1ll * n * n;
n /= r;
ll kx = 1ll * (n + 1) / 2;
ll k1 = kx * kx;
kx = 1ll * n / 2;
k1 += kx * kx;
k1 *= r * r;
ll k2 = S - k1;
ll v1 = 0, v2 = 0;
for(int i = 0; i < m; i++)
{
ll pl = 1ll * (l2[i] - l1[i] + 1) * (r2[i] - r1[i] + 1);
ll c1 = solve(r, l1[i], r1[i], l2[i], r2[i], 1);
ll c2 = solve(r, l1[i], r1[i], l2[i], r2[i], 0);
// cout << r << " " << solve(r, l1[i], r1[i], l2[i], r2[i], 1) << endl;
v1 += c1;
k1 -= (pl - c1);
v2 += c2;
k2 -= (pl - c2);
}
ans = min(ans, min(v1 + k1, v2 + k2));
}
cout << ans;
}
Compilation message
chessboard.cpp: In function 'void DFS(int, long long int)':
chessboard.cpp:44:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i == ve.size())
~~^~~~~~~~~~~~
chessboard.cpp: In function 'int32_t main()':
chessboard.cpp:215:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < pr.size() && pr[j] * i < N && pr[j] <= lp[i]; j++)
~~^~~~~~~~~~~
chessboard.cpp:223:17: error: 'get_ans' was not declared in this scope
cout << get_ans(1, n);
^~~~~~~
chessboard.cpp:223:17: note: suggested alternative: 'wctrans'
cout << get_ans(1, n);
^~~~~~~
wctrans
