**Tutorial**

Tutorial is loading...

**Solution (PikMike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for(int i = 0; i < int(n); i++)
using namespace std;
int main() {
long long n, m;
int a, b;
cin >> n >> m >> a >> b;
cout << min(n % m * b, (m - n % m) * a) << endl;
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
#include<bits/stdc++.h>
using namespace std;
const int N = 200 * 1000 + 555;
int n, k, a[N];
inline bool read() {
if(!(cin >> n >> k))
return false;
for(int i = 0; i < n; i++)
assert(scanf("%d", &a[i]) == 1);
return true;
}
inline void solve() {
sort(a, a + n);
a[n++] = int(2e9);
int ans = 0, u = 0;
for(int i = 0; i < n - 1; i++) {
while(u < n && a[i] == a[u])
u++;
if(a[u] - a[i] > k)
ans++;
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
#endif
}
return 0;
}
```

990C - Bracket Sequences Concatenation Problem

**Tutorial**

Tutorial is loading...

**Solution (Ajosteen)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 7;
int n;
string s[N];
char buf[N];
int cnt[N];
int getBalance(string &s){
int bal = 0;
for(int i = 0; i < s.size(); ++i){
if(s[i] == '(')
++bal;
else
--bal;
if(bal < 0)
return -1;
}
return bal;
}
string rev(string &s){
string revs = s;
reverse(revs.begin(), revs.end());
for(int i = 0; i < revs.size(); ++i)
if(revs[i] == '(')
revs[i] = ')';
else
revs[i] = '(';
return revs;
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%s", buf);
s[i] = buf;
}
for(int i = 0; i < n; ++i){
int bal = getBalance(s[i]);
if(bal != -1)
++cnt[bal];
}
long long res = 0;
for(int i = 0; i < n; ++i){
s[i] = rev(s[i]);
int bal = getBalance(s[i]);
if(bal != -1)
res += cnt[bal];
}
printf("%I64d\n", res);
return 0;
}
```

990D - Graph And Its Complement

**Tutorial**

Tutorial is loading...

**Solution (Ajosteen)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = int(1e3) + 7;
int n, a, b;
bool mat[N][N];
int main(){
scanf("%d %d %d", &n, &a, &b);
if(min(a, b) > 1){
puts("NO");
return 0;
}
if(a == 1 && b == 1){
if(n == 2 || n == 3){
puts("NO");
return 0;
}
puts("YES");
for(int i = 1; i < n; ++i)
mat[i][i - 1] = mat[i - 1][i] = true;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j)
printf("%c", '0' + mat[i][j]);
puts("");
}
return 0;
}
bool x = false;
if(a == 1){
swap(a, b);
x = true;
}
for(int i = n - a; i > 0; --i)
mat[i][i - 1] = mat[i - 1][i] = true;
puts("YES");
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j)
printf("%c", '0' + ((x ^ mat[i][j]) && (i != j)));
puts("");
}
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution (PikMike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int INF = 1e9;
const long long INF64 = 1e18;
const int N = 1000 * 1000 + 13;
int n, m, k;
bool pos[N];
int lst[N], s[N], a[N];
int get(int l){
int r = 0, i = -1, res = 0;
while (r < n){
if (lst[r] <= i)
return INF;
i = lst[r];
r = lst[r] + l;
++res;
}
return res;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
forn(i, m) scanf("%d", &s[i]);
forn(i, k) scanf("%d", &a[i]);
forn(i, n) pos[i] = true;
forn(i, m) pos[s[i]] = false;
forn(i, n){
if (pos[i])
lst[i] = i;
else if (i)
lst[i] = lst[i - 1];
else
lst[i] = -1;
}
long long ans = INF64;
forn(i, k){
long long t = get(i + 1);
if (t != INF)
ans = min(ans, a[i] * t);
}
printf("%lld\n", ans == INF64 ? -1 : ans);
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution (PikMike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
mt19937 rnd(time(NULL));
const int N = 1'000'013;
int n, m;
pair<int, int> e[N];
int a[N], rk[N];
long long sum[N], ans[N];
int p[N];
int getP(int a){
return (a == p[a] ? a : p[a] = getP(p[a]));
}
bool merge(int a, int b){
a = getP(a);
b = getP(b);
if (a == b) return false;
if (rk[a] > rk[b]) swap(a, b);
p[a] = b;
rk[b] += rk[a];
return true;
}
bool used[N];
vector<int> g[N];
int h[N];
void dfs(int v, int p){
sum[v] = a[v];
for (auto u : g[v]){
if (u != p){
h[u] = h[v] + 1;
dfs(u, v);
sum[v] += sum[u];
}
}
}
int main() {
scanf("%d", &n);
forn(i, n)
scanf("%d", &a[i]);
forn(i, n) p[i] = i, rk[i] = 1;
scanf("%d", &m);
forn(i, m){
int &v = e[i].first;
int &u = e[i].second;
scanf("%d%d", &v, &u);
--v, --u;
if (merge(v, u)){
g[v].push_back(u);
g[u].push_back(v);
used[i] = true;
}
}
long long tot = 0;
forn(i, n) tot += a[i];
if (tot != 0){
puts("Impossible");
return 0;
}
dfs(0, -1);
puts("Possible");
forn(i, m){
if (used[i]){
int v = e[i].first, u = e[i].second;
if (h[v] < h[u])
ans[i] = sum[u];
else
ans[i] = -sum[v];
}
printf("%lld\n", ans[i]);
}
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution with Möbius (Bleddest)**

```
#include<bits/stdc++.h>
using namespace std;
const int N = 200043;
int d[N];
void sieve()
{
vector<int> pr;
for(int i = 2; i < N; i++)
{
if (d[i] == 0)
{
d[i] = i;
pr.push_back(i);
}
for(auto x : pr)
{
if (x > d[i] || x * 1ll * i >= N)
break;
d[i * x] = x;
}
}
}
int mobius(int x)
{
int last = -1;
int res = 1;
while(x != 1)
{
if(last == d[x])
res = 0;
else
res = -res;
last = d[x];
x /= d[x];
}
return res;
}
int mb[N];
vector<int> need_bfs[N];
int used[N];
vector<int> g[N];
int a[N];
int cc = 0;
int q[N];
int hd, tl;
int good[N];
int bfs(int x, int gc)
{
hd = 0;
tl = 0;
q[tl++] = x;
used[x] = cc;
while(hd < tl)
{
int z = q[hd++];
for(auto y : g[z])
{
if(good[a[y]] == cc && used[y] < cc)
{
used[y] = cc;
q[tl++] = y;
}
}
}
return tl;
}
long long ans1[N];
long long ans2[N];
int main() {
sieve();
for(int i = 1; i < N; i++)
mb[i] = mobius(i);
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
for(int i = 0; i < n - 1; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 0; i < n; i++)
{
need_bfs[a[i]].push_back(i);
}
for(int i = 200000; i >= 1; i--)
{
cc++;
for(int j = i; j <= 200000; j += i)
good[j] = cc;
for(int j = i; j <= 200000; j += i)
for(auto x : need_bfs[j])
{
if(used[x] == cc) continue;
int z = bfs(x, i);
ans1[i] += z * 1ll * (z + 1) / 2;
}
for(int j = i, k = 1; j <= 200000; j += i, k++)
ans2[i] += mb[k] * ans1[j];
}
for(int i = 1; i <= 200000; i++)
if(ans2[i])
printf("%d %lld\n", i, ans2[i]);
return 0;
}
```

**Solution with centroid (adedalic)**

```
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream &out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream &out, const vector<A> &v) {
out << "[";
for(auto &e : v)
out << e << ", ";
return out << "]";
}
const int N = 1000 * 1000 + 555;
const int LOGN = 21;
int mind[N];
int pw[LOGN][N];
int n, a[N];
vector<int> g[N];
li res[N];
bool gen() {
mt19937 rnd(42);
n = 200 * 1000;
fore(i, 0, n)
a[i] = 831600;
fore(i, 1, n) {
int u = rnd() % i, v = i;
g[u].push_back(v);
g[v].push_back(u);
}
return true;
}
inline bool read() {
// return gen();
if(!(cin >> n))
return false;
fore(i, 0, n)
assert(scanf("%d", &a[i]) == 1);
fore(i, 0, n - 1) {
int u, v;
assert(scanf("%d%d", &u, &v) == 2);
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
return true;
}
vector<pt> dv[N];
inline int gcd(int a, int b) {
int ans = 1;
unsigned int u = 0, v = 0;
while(u < dv[a].size() && v < dv[b].size()) {
if(dv[a][u].x < dv[b][v].x)
u++;
else if(dv[a][u].x > dv[b][v].x)
v++;
else {
ans *= pw[min(dv[a][u].y, dv[b][v].y)][dv[a][u].x];
u++, v++;
}
}
return ans;
}
bool used[N];
int sz[N];
void calcSz(int v, int p) {
sz[v] = 1;
for(int to : g[v]) {
if(to == p || used[to])
continue;
calcSz(to, v);
sz[v] += sz[to];
}
}
int findC(int v, int p, int all) {
for(int to : g[v]) {
if(to == p || used[to])
continue;
if(sz[to] > all / 2)
return findC(to, v, all);
}
return v;
}
int u[N], T = 0;
int cntD[N];
inline void addDiv(int d, int cnt) {
if(u[d] != T)
u[d] = T, cntD[d] = 0;
cntD[d] += cnt;
}
int cds[N], szcds;
void calcDs(int v, int p, int gc) {
gc = gcd(a[v], gc);
cds[szcds++] = gc;
for(int to : g[v]) {
if(to == p || used[to])
continue;
calcDs(to, v, gc);
}
}
vector<int> cps, cmx, vmx;
void check(int curd, int curg, int pos, int add) {
if(pos >= (int)cps.size()) {
if(u[curd] == T)
res[curg] += cntD[curd] * 1ll * add;
return;
}
fore(st, 0, cmx[pos] + 1) {
check(curd, curg, pos + 1, add);
curd *= cps[pos];
if(st < vmx[pos])
curg *= cps[pos];
}
}
pt ops[N]; int szops;
int cntDiff[N];
void calc(int v) {
calcSz(v, -1);
int c = findC(v, -1, sz[v]);
used[c] = 1;
// cerr << "C = "<< c << endl;
cps.resize(dv[a[c]].size());
cmx.resize(cps.size());
vmx.resize(cmx.size());
fore(i, 0, cps.size()) {
cps[i] = dv[a[c]][i].x;
cmx[i] = dv[a[c]][i].y;
}
T++;
addDiv(a[c], 1);
for(int to : g[c]) {
if(used[to]) continue;
szcds = 0;
calcDs(to, c, a[c]);
fore(i, 0, szcds)
cntDiff[cds[i]]++;
szops = 0;
fore(j, 0, szcds) {
if(cntDiff[cds[j]] == 0)
continue;
int p = 0, val = cds[j];
fore(i, 0, vmx.size()) {
if(p >= (int)dv[val].size() || dv[val][p].x > cps[i])
vmx[i] = 0;
else
vmx[i] = dv[val][p].y, p++;
}
check(1, 1, 0, cntDiff[cds[j]]);
ops[szops++] = {cds[j], cntDiff[cds[j]]};
cntDiff[cds[j]] = 0;
}
fore(j, 0, szops)
addDiv(ops[j].x, ops[j].y);
}
for(int to : g[c]) {
if(used[to]) continue;
calc(to);
}
}
inline void solve() {
iota(mind, mind + N, 0);
fore(i, 2, N) {
if(mind[i] != i)
continue;
pw[0][i] = 1;
fore(st, 1, LOGN)
pw[st][i] = pw[st - 1][i] * i;
for(li j = i * 1ll * i; j < N; j += i)
mind[j] = min(mind[j], i);
}
fore(i, 2, N) {
int val = i;
while(mind[val] > 1) {
if(dv[i].empty() || dv[i].back().x != mind[val])
dv[i].emplace_back(mind[val], 0);
dv[i].back().y++;
val /= mind[val];
}
}
memset(res, 0, sizeof res);
T = 0;
calc(0);
fore(i, 0, n)
res[a[i]]++;
fore(i, 1, 1000'000 + 1) {
if(res[i])
printf("%d %lld\n", i, res[i]);
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
#endif
}
return 0;
}
```