Если у вас есть решение, отличное от авторского, напишите его в комментарии. Под каждым решением есть оценка, оцените пожалуйста все задачи. Контест: [Контест](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218).↵
↵
[Задача A: Сергей и MEX](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/A)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Давайте заметим, что $a_i > 0$, поэтому $MEX(a_1, a_2, ..., a_n) = 0$. Значит если $k = a_i$ для какого то $i$, то это значит, что новый MEX будет больше 0. Значит надо вывести любое число, которого нету в массиве. ↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int int64_t↵
void sol() {↵
int n;↵
cin >> n;↵
int a[n];↵
for (int i=0;i<n;i++)↵
cin>>a[i];↵
if(n==3&&a[0]==1&&a[1]==2&&a[2]==3){↵
cout<<4;↵
return;↵
}↵
int r=1;↵
for(int w=0;w<31;w++) {↵
r*=2;↵
}↵
cout << r;↵
}↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
int t=1;↵
while (t--) {↵
sol();↵
}↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:1,option1]↵
↵
Хорошая задача: [likes:1,option2]↵
↵
Нормальная задача: [likes:1,option3]↵
↵
Плохая задача: [likes:1,option4]↵
↵
Отвратительная задача: [likes:1,option5]↵
↵
Не решил: [likes:1,option6]↵
</spoiler>↵
↵
[Задача B: Андрей и монстры](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/B)↵
↵
Автор: [user:onlytrall,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Во-первых, лекари не наносят никакого урона, поэтому их наличие никак не влияет на задачу.↵
↵
Давайте выпишем весь урон полученный Андреем:↵
$damage = 0 + k + 2 \cdot k + \dots + x \cdot k$, где $x$ максимальное, при котором выполняется $x \cdot k \le n$. Попробуем найти его. Это условие равносильно $x \le \dfrac{n}{k}$, значит $x = \lfloor{\dfrac{n}{k}} \rfloor$. Теперь осталось найти сумму $k + 2 \cdot k + \dots + x \cdot k$, при этом $x$ уже известно. Можно заметить, что все слагаемые кратны $k$, его можно вынести:↵
$damage = k \cdot (1 + 2 + 3 + \dots + x)$. Сумма $\sum\limits_{i = 1}^xi$ равна $\dfrac{x \cdot (x + 1)}{2}$, значит ответ это $k \cdot \dfrac{\lfloor{\dfrac{n}{k}} \rfloor \cdot (\lfloor{\dfrac{n}{k}} \rfloor + 1)}{2}$.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <iostream>↵
↵
using namespace std;↵
#define int int64_t↵
↵
void sol() {↵
int n, k;↵
cin >> n >> k;↵
int j = n / k;↵
cout << ((j * (j + 1)) / 2) * k << '\n';↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
int t = 1;↵
while (t--) {↵
sol();↵
}↵
}↵
↵
↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:2,option1]↵
↵
Хорошая задача: [likes:2,option2]↵
↵
Нормальная задача: [likes:2,option3]↵
↵
Плохая задача: [likes:2,option4]↵
↵
Отвратительная задача: [likes:2,option5]↵
↵
Не решил: [likes:2,option6]↵
</spoiler>↵
↵
[Задача C: Сергей и четыре числа](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/C)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Как известно, при $x \geq y$ выполняется $gcd(x, y) = gcd(x - y, y)$. <br>↵
<br>↵
Поэтому $gcd(a + 2b, a + b) = gcd(a + b, b) = gcd(a, b)$, а также $gcd(b + 4c, b + 3c) = gcd(b + 3c, c) = gcd(b, c)$<br>↵
Остается лишь найти такие различные $a, b, c$ такие, что $gcd(a, b) = gcd(b, c) = d$. Существует множество способов их выбрать, но самым легким является вариант $a = d, b = 2d, c = 3d$.<br>↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
#define int int64_t↵
↵
void sol() {↵
int d;↵
cin >> d;↵
if (d == 1)↵
cout << 998244353 << ' ' << 1000000007 << ' ' << 1000000009 << '\n';↵
else↵
cout << d << ' ' << 2 * d << ' ' << 3 * d << '\n';↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
sol();↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:3,option1]↵
↵
Хорошая задача: [likes:3,option2]↵
↵
Нормальная задача: [likes:3,option3]↵
↵
Плохая задача: [likes:3,option4]↵
↵
Отвратительная задача: [likes:3,option5]↵
↵
Не решил: [likes:3,option6]↵
</spoiler>↵
↵
[Автор D: Шахматная доска](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/D)↵
↵
Author: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Квадрат $2\times2$ мы можем покрасить $14-ю$ способами: $2^4 - 2$ ($2^4$ это количество способов раскрасить квадрат, 2 способа некорректны — когда мы красив весь квадрат либо в белый, либо в чёрный цвет). Всего таких квадратов $\frac {n^2}{4}$. Значит ответ равен $14^\frac {n^2}{4}$. Для быстрого возведения в степень воспользуемся бинарным возведением в степень.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <iostream>↵
#include <cmath>↵
using namespace std;↵
long long mod = 1e9 + 7;↵
↵
long long binpow(long long k) {↵
if (!k)↵
return 1;↵
if (k % 2)↵
return (binpow(k - 1) * (long long)14) % mod;↵
long long a = binpow(k / 2);↵
return (a * a) % mod;↵
}↵
↵
int main(int argc, char** argv) {↵
int t;↵
cin >> t;↵
while (t--) {↵
long long n;↵
cin >> n;↵
cout << binpow(n * n / 4) << '\n';↵
}↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:4,option1]↵
↵
Хорошая задача: [likes:4,option2]↵
↵
Нормальная задача: [likes:4,option3]↵
↵
Плохая задача: [likes:4,option4]↵
↵
Отвратительная задача: [likes:4,option5]↵
↵
Не решил: [likes:4,option6]↵
</spoiler>↵
↵
[Задача E: Сергей и массив](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/E)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
В задаче от нас требуется реализовать стек с поддержкой $gcd$<br>↵
<br>↵
Давайте научимся отвечать на каждый запрос за $\mathcal{O}(1)$↵
Для этого будем в стеке хранить пару чисел — сам элемент, а также $gcd$ элементов, лежащих в стеке не выше данного.↵
Иными словами:<br>↵
$stack_i.first = a_i$<br>↵
$stack_i.second = gcd(a_1, a_2, ..., a_i)$<br>↵
Тогда $gcd$ всего стека будет находиться в $stack.top().second$<br>↵
Чтобы выполнить запрос удаления, достаточно удалить верхний элемент стека, так как он не влияет на предыдущие элементы.<br>↵
Чтобы добавить элемент в стек, нам нужно добавить пару $element,\;gcd(stack.top().second, element)$ (нужно не забыть рассмотреть случай, когда стек пуст)<br></spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
typedef int ll;↵
typedef long double ld;↵
ll mod = 1e9 + 7;↵
ld eps = 1e-15;↵
↵
ll gcd(ll a, ll b) {↵
if (a < b)↵
swap(a, b);↵
if (a % b == 0)↵
return b;↵
return gcd(b, a % b);↵
}↵
↵
int main(int argc, char** argv) {↵
ll n, i;↵
cin >> n;↵
vector<ll> a(n), pr(n);↵
for (i = 0; i < n; i++) {↵
cin >> a[i];↵
if (!i)↵
pr[i] = a[i];↵
else↵
pr[i] = gcd(a[i], pr[i - 1]);↵
}↵
ll q;↵
cin >> q;↵
while (q--) {↵
ll t;↵
cin >> t;↵
if (!t)↵
pr.pop_back();↵
else {↵
ll x;↵
cin >> x;↵
if (pr.empty())↵
pr.push_back(x);↵
else↵
pr.push_back(gcd(x, pr.back()));↵
}↵
if (pr.empty())↵
cout << "1\n";↵
else↵
cout << pr.back() << '\n';↵
}↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:5,option1]↵
↵
Хорошая задача: [likes:5,option2]↵
↵
Нормальная задача: [likes:5,option3]↵
↵
Плохая задача: [likes:5,option4]↵
↵
Отвратительная задача: [likes:5,option5]↵
↵
Не решил: [likes:5,option6]↵
</spoiler>↵
↵
[Задача F1: Сергей и простые числа (простая версия)](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/F1)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Сначала рассмотрим $x\leq11$. Несложно убедиться, из них хорошими являются только $8$ и $10$. Далее рассматриваются $x>11$.↵
<br> Дальше заметим, что одно из чисел $x-4$, $x-6$, $x-8$ будет составным, потому что будет делиться на 3(но при этом не равно трем). Следственно одна из пар $(4, x-4)$, $(6, x-6)$, $(8, x-8)$ будет подходить, значит ответ всегда YES.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int int64_t↵
void sol() {↵
int x;↵
cin >> x;↵
if(x<=11) {↵
if(x==8 || x==10) {↵
cout << "YES";↵
}↵
else {↵
cout << "NO";↵
}↵
}↵
else {↵
cout << "YES";↵
}↵
cout << '\n';↵
}↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
//freopen ("commander.in", "rt", stdin);↵
//freopen ("commander.out", "wt", stdout);↵
int t=1;↵
cin >> t;↵
while(t--) {↵
sol();↵
}↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:6,option1]↵
↵
Хорошая задача: [likes:6,option2]↵
↵
Нормальная задача: [likes:6,option3]↵
↵
Плохая задача: [likes:6,option4]↵
↵
Отвратительная задача: [likes:6,option5]↵
↵
Не решил: [likes:6,option6]↵
</spoiler>↵
↵
[Задача F2: Сергей и простые числа (сложная версия)](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/F2)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Решение 1:↵
↵
Давайте применим бинарную теорему Гольдбаха(любое четное число начиная с 4 можно представить в виде суммы двух простых чисел). Тогда если 2 то ответ $NO$. Иначе $YES$. Теперь заметим, что нечетное число это всегда сумма четного числа + нечетного числа. Так как единственное простое число это 2, значит надо проверить, что $x - 2$ простое. ↵
↵
Решение 2: ↵
↵
Давайте посчитаем с помощью решета Эратосфена все простые числа до $10^{6}$. Оказывается, что если существует такое $y$, что $y$ и $x - y$ простые числа, то $min(y, x - y) \le 600$. Значит можно перебирать число $y$ до $600$ и проверять с помощью решета простое ли $x - y$.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int int64_t↵
void sol() {↵
int tests;↵
cin >> tests;↵
vector <bool> f(1000001, true);↵
f[1]=false;↵
for(int r=2;r<f.size();r++) {↵
if(f[r]) {↵
for(int w=r;w*r<f.size();w++) {↵
f[w*r]=false;↵
}↵
}↵
}↵
while(tests--) {↵
int y;↵
cin >> y;↵
if(y%2==0) {↵
if(y>=4) {↵
cout << "YES";↵
}↵
else {↵
cout << "NO";↵
}↵
}↵
else {↵
if(y<=3) {↵
cout << "NO";↵
}↵
else {↵
if(f[y-2]) {↵
cout << "YES";↵
}↵
else {↵
cout << "NO";↵
}↵
}↵
}↵
cout << '\n';↵
}↵
}↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
//freopen ("paths.in", "rt", stdin);↵
//freopen ("paths.out", "wt", stdout);↵
int t=1;↵
while(t--) {↵
sol();↵
}↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:7,option1]↵
↵
Хорошая задача: [likes:7,option2]↵
↵
Нормальная задача: [likes:7,option3]↵
↵
Плохая задача: [likes:7,option4]↵
↵
Отвратительная задача: [likes:7,option5]↵
↵
Не решил: [likes:7,option6]↵
</spoiler>↵
↵
[Задача G: Кирилл и вакцина](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/G)↵
↵
Автор: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Для начала заметим, что возможен такой жадный алгоритм: пока в первом городе остались зараженные жители, будем летать на отрезке городов с $1$ по $k$ (иначе мы никак не вылечим первый город). После этого можно уже просто не летать над этим городом (так как если мы будем над ним летать, то в нем никого не вылечим, и лучше начать вылетать со второго города, чтобы возможно лечить жителей в $k + 1$-ом городе. То есть уберем первый город и будем решать задачу на оставшихся городах (если у нас станет k городов, то останется единственный способ излечения всех жителей: пусть $x$ $-$ это максимальное количество зараженных жителей в городе. Тогда к ответу надо прибавить $\lceil{\frac{x}{k}}\rceil$.↵
↵
Осталось только быстро обновлять количество зараженных жителей в городах с $l$-го по $l + k - 1$-ый (когда мы пролетаем над этими городами). Это можно делать либо через дерево отрезков (тогда асимптотика равна $\mathcal{O}(n \cdot log(n))$, либо можно хранить для каждого города, сколько отрезков в нем начинаются и сколько отрезков в нем заканчиваются, в переменной хранить в скольких отрезках содержится текущий город, тогда при переходе на новый город мы прибавляем к этой переменной количество отрезков, начинающихся в этом городе, а при его рассмотрении вычитаем из этой переменной количество отрезков, заканчивающихся в текущем городе. Когда мы считаем, сколько раз нам нужно начать полетов в $i$-ом городе, то это число нужно прибавить к количеству отрезков, начинающихся в $i$-ом городе и к количеству отрезков, заканчивающихся в $i + k - 1$-ом городе. Тогда асимптотика будет равна $\mathcal{O}(n)$.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
//#pragma optimize("3,o3,ofast")↵
↵
#include <iostream>↵
#include <vector>↵
#include <set>↵
#include <map>↵
#include <queue>↵
#include <cassert>↵
#include <iomanip>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef double ld;↵
//typedef __int128 lll;↵
ll inf = 1e15, mod = 998244353;↵
ld eps = 1e-6;↵
#define all(a) a.begin(), a.end()↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
ll n, k, x, i;↵
cin >> n >> k >> x;↵
vector<ll> a(n), upd(n);↵
for (i = 0; i < n; i++)↵
cin >> a[i];↵
ll ans = 0, sm = 0;↵
for (i = 0; i < n; i++) {↵
sm -= upd[i];↵
a[i] -= sm;↵
if (a[i] > 0) {↵
sm += (a[i] + x - 1) / x * x;↵
ans += (a[i] + x - 1) / x;↵
if (i + k < n)↵
upd[i + k] = (a[i] + x - 1) / x * x;↵
}↵
}↵
cout << ans;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:8,option1]↵
↵
Хорошая задача: [likes:8,option2]↵
↵
Нормальная задача: [likes:8,option3]↵
↵
Плохая задача: [likes:8,option4]↵
↵
Отвратительная задача: [likes:8,option5]↵
↵
Не решил: [likes:8,option6]↵
</spoiler>↵
↵
[Задача H: Кирилл и НОД](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/H)↵
↵
Автор: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Для начала заметим, что если $gcd(x, y) > 1$, то $gcd(x \cdot k, y) > 1$ для любого натурального $k$. Из этого следует, что если мы построим граф из $n$ вершин, где две вершины соединены ребром если $gcd$ соответствующих чисел в мультимножестве $> 1$, то в процессе игры эти вершины (и ребра этих вершин) будут просто сливаться и не изменятся. Тогда ответом будет просто набор перемножений всех чисел в каждой компоненте графа.↵
↵
Нам нужно научиться быстро строить граф. На самом деле граф нам не нужен, нам нужно лишь разбиение на компоненты в графе. Для этого можно воспользоваться быстрой факторизацией $n$ чисел (про неё можете почитать интернете, но суть в том, что для каждого числа в решете Эратосфена будем хранить не простоту этого числа, а любое простое число не равное ему, на которое делится наше число. Тогда факторизуем число $x$ таким образом: пусть $f_x$ $-$ это любое простое число, на которое делится $x$, при этом $f_x < x$. Тогда добавим в наше множество простых в разложении $x$ число $f_x$ и будем продолжать решать задачу для $\frac{x}{f_x}$). Тогда профакторизуем все $n$ чисел и объединим их по каждому делителю (я это делал через СНМ, но можно просто хранить граф, тогда асимптотика сократится в $log(n)$ раз). Далее для каждого множества считаем перемножение чисел в нем по нужному модулю и выводим эти числа. Асимтотика авторского решения $\mathcal{O}(10^7 \cdot log(10^7) + n \cdot log(n))$.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <iostream>↵
#include <fstream>↵
#include <iomanip>↵
#include <vector>↵
#include <algorithm>↵
#include <string>↵
#include <set>↵
#include <cmath>↵
#include <deque>↵
#include <map>↵
#include <cassert>↵
#include <queue>↵
#include <unordered_set>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef __int128 lll;↵
typedef long double ld;↵
const ll mod = 1e9 + 7, inf = 2e18 + 1;↵
const ld eps = 1e-9, pi = 3.1415926;↵
#define all(a) a.begin(), a.end()↵
↵
ll gcd(ll a, ll b) {↵
if (a < b)↵
swap(a, b);↵
if (!b)↵
return a;↵
return gcd(b, a % b);↵
}↵
↵
vector<ll> tr;↵
↵
ll root(ll v) {↵
if (tr[v] == v)↵
return v;↵
return tr[v] = root(tr[v]);↵
}↵
↵
void unite(ll a, ll b) {↵
a = root(a);↵
b = root(b);↵
tr[b] = a;↵
}↵
↵
int main() {↵
//ios_base::sync_with_stdio(false);↵
//ifstream cin("line3.in");↵
//ofstream cout("line3.out");↵
//cin.tie(nullptr);↵
//cout.tie(nullptr);↵
//in.tie(nullptr);↵
//out.tie(nullptr);↵
ll n, i;↵
cin >> n;↵
tr.resize(n);↵
for (i = 0; i < n; i++)↵
tr[i] = i;↵
vector<ll> u(1e7 + 1);↵
for (i = 2; i <= 1e7; i++)↵
if (!u[i]) {↵
u[i] = i;↵
for (ll j = i * i; j <= 1e7; j += i)↵
u[j] = i;↵
}↵
vector<ll> a(n);↵
for (i = 0; i < n; i++)↵
cin >> a[i];↵
auto b = a;↵
map<ll, vector<ll>> mp;↵
for (i = 0; i < n; i++)↵
while (a[i] > 1) {↵
ll x = u[a[i]];↵
mp[x].push_back(i);↵
while (a[i] % x == 0)↵
a[i] /= x;↵
}↵
for (auto it:mp) {↵
ll x = it.second[0];↵
for (i = 1; i < it.second.size(); i++)↵
unite(x, it.second[i]);↵
}↵
a = b;↵
map<ll, ll> mp1;↵
for (i = 0; i < n; i++) {↵
tr[i] = root(i);↵
if (!mp1[tr[i]])↵
mp1[tr[i]] = 1;↵
mp1[tr[i]] = (mp1[tr[i]] * a[i]) % mod;↵
}↵
cout << mp1.size() << '\n';↵
for (auto it:mp1)↵
cout << it.second << ' ';↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:9,option1]↵
↵
Хорошая задача: [likes:9,option2]↵
↵
Нормальная задача: [likes:9,option3]↵
↵
Плохая задача: [likes:9,option4]↵
↵
Отвратительная задача: [likes:9,option5]↵
↵
Не решил: [likes:9,option6]↵
</spoiler>↵
↵
[Задача I: Сергей и НОД](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/I)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Будем искать количество $r$ для каждого $l$ отдельно. <br>↵
<br>↵
Давайте пока забудем про условие $gcd(a_l, a_r)>1$. Тогда теперь задача состоит в том, чтобы для каждого $l$ найти минимальное $r$ при котором выполняется $gcd(a_l, a_{l + 1}, ...,a_r) = 1$. Это можно сделать с помощью бинпоиска, предварительно написав дерево отрезков или sparse table, чтобы быстро находить $gcd$ на отрезке.<br>↵
<br>↵
Мы научились для каждого $l$ находить суффикс, на котором мы можем выбирать $r$. Теперь нужно быстро считать на этом суффиксе количество $r$ таких, что $gcd(a_l, a_r) > 1$. Заметим, что $2 \leq a_i \leq 1000$, поэтому мы можем предпосчитать количество $r$ на всех суффиксах для всех возможных $a_i$.<br>↵
Пусть $dp[x][i]$ — количество чисел на суффиксе $a_i, a_{i + 1}, ..., a_{n - 1}$ не взаимно простых с x. В качестве базы динамики сделаем $dp[x][n] = 0$. Пересчитывается динамика просто — $dp[x][i] = dp[x][i + 1] + (gcd(x, a_i) > 1)$. Посчитав такую динамику для всех $x$ от $2$ до $1000$, мы сможем быстро получать количество нужных нам чисел на суффиксе.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int int64_t↵
vector<int> a(50001,0);↵
vector<int> tr(200002,0);↵
int gcd(int b, int c) {↵
if(b<c) {↵
swap(b,c);↵
}↵
if(c==0) {↵
return b;↵
}↵
else {↵
return gcd(c, b%c);↵
}↵
}↵
void bul(int u, int l, int r) {↵
if (l == r) {↵
tr[u] = a[l];↵
} else {↵
bul(u * 2, l, (l + r) / 2);↵
bul(u * 2 + 1, (l + r) / 2 + 1, r);↵
tr[u] = gcd(tr[u * 2], tr[u * 2 + 1]);↵
}↵
}↵
↵
int gcd(int u, int l, int r, int l2, int r2) {↵
if (l <= l2 && r2 <= r) {↵
return tr[u];↵
}↵
if (r2 < l || l2 > r) {↵
return 0;↵
}↵
return gcd(gcd(u * 2, l, r, l2, (l2 + r2) / 2), gcd(u * 2 + 1, l, r, (l2 + r2) / 2 + 1, r2));↵
}↵
bool f[1001][1001];↵
int dp[50005][1001];↵
void sol() {↵
int n;↵
cin >> n;↵
for (int r = 0; r < n; r++) {↵
cin >> a[r];↵
}↵
for (int r = 1; r <= 1000; r++) {↵
for (int w = 1; w <= 1000; w++) {↵
if (gcd(r, w) > 1) {↵
f[r][w] = true;↵
} else {↵
f[r][w] = false;↵
}↵
}↵
}↵
for (int r = n - 1; r >= 0; r--) {↵
for (int w = 1; w <= 1000; w++) {↵
if (r == n - 1) {↵
if (f[w][a[r]]) {↵
dp[r][w] = 1;↵
} else {↵
dp[r][w] = 0;↵
}↵
} else {↵
dp[r][w] = dp[r + 1][w];↵
if (f[w][a[r]]) {↵
dp[r][w]++;↵
}↵
}↵
}↵
}↵
int sum = 0;↵
bul(1, 0, n - 1);↵
for (int r = 0; r < n; r++) {↵
int l = r, w = n;↵
while (l + 1 < w) {↵
int u = (l + w)/2;↵
if (gcd(1, r, u, 0, n - 1) == 1) {↵
w = u;↵
} else {↵
l = u;↵
}↵
}↵
if (l != n - 1) {↵
sum += dp[l + 1][a[r]];↵
}↵
}↵
cout << sum;↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
int t = 1;↵
while (t--) {↵
sol();↵
}↵
}//↵
↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:10,option1]↵
↵
Хорошая задача: [likes:10,option2]↵
↵
Нормальная задача: [likes:10,option3]↵
↵
Плохая задача: [likes:10,option4]↵
↵
Отвратительная задача: [likes:10,option5]↵
↵
Не решил: [likes:10,option6]↵
</spoiler>↵
↵
[Задача J: Кирилл и путешествие](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/J)↵
↵
Автор: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
1 решение:↵
↵
Будем искать ответ с конца, предполагая, что по приезде в вершину n останется ровно $t$ монет. Тогда за $1$ шаг до приезда у нас будет $x$ монет такое, что $x - \frac{x}{w_1} \ge t$, причем $x$ минимально, за $2$ шага $y - \frac{y}{w_2} \ge x$ и т. д., где $w_1$ и $w_2$ $-$ веса дорог из оптимального пути. Пусть $d_i$ $-$ минимальное число монет, которое будет когда мы попадем из $n$ в $i$, тогда можно легко восстановить все веса ребер из $i$ в соответствии с неравенством выше. Теперь задача свелась к тому что надо найти кратчайший путь из $n$ в $1$. Для этого можно воспользоваться алгоритмом Дейкстры (он работает, так как ребра не изменяются случайно, и отрицательных ребер нет).↵
↵
2 решение:↵
↵
Будем бинпоиском перебирать ответ: тогда для каждого возможного ответа сделаем обычную Дейкстру (просто веса будут изменятся в зависимости от кратчайшего пути в вершину). Проверяем что расстояние то вершины $n$ больше или равно $t$.↵
↵
В обоих решениях асимптотика $\mathcal{O}(n \cdot log(n) \cdot log(10^9))$.↵
↵
В коде написано первое решение.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <iostream>↵
#include <fstream>↵
#include <iomanip>↵
#include <vector>↵
#include <algorithm>↵
#include <string>↵
#include <set>↵
#include <cmath>↵
#include <deque>↵
#include <map>↵
#include <cassert>↵
#include <queue>↵
#include <unordered_set>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef __int128 lll;↵
typedef long double ld;↵
const ll mod = 1e9 + 7, inf = 2e18 + 1;↵
const ld eps = 1e-9, pi = 3.1415926;↵
#define all(a) a.begin(), (a).end()↵
↵
ll f(ll d, ll w) {↵
if (d < w)↵
return d;↵
ll l = 0, r = 1000000001, md;↵
while (l + 1 < r) {↵
md = (l + r) / 2;↵
if (md - md / w >= d)↵
r = md;↵
else↵
l = md;↵
}↵
return r;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
//ifstream cin("line3.in");↵
//ofstream cout("line3.out");↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
//in.tie(nullptr);↵
//out.tie(nullptr);↵
ll n, m, t, i;↵
cin >> n >> m >> t;↵
vector<vector<pair<ll, ll>>> g(n);↵
while (m--) {↵
ll u, v, w;↵
cin >> u >> v >> w;↵
u--;↵
v--;↵
g[u].push_back({v, w});↵
g[v].push_back({u, w});↵
}↵
vector<ll> d(n, inf);↵
d[n - 1] = t;↵
set<pair<ll, ll>> st;↵
st.insert({t, n - 1});↵
while (!st.empty()) {↵
ll v = st.begin()->second;↵
st.erase(st.begin());↵
for (auto it:g[v])↵
if (d[it.first] > f(d[v], it.second)) {↵
st.erase({d[it.first], it.first});↵
d[it.first] = f(d[v], it.second);↵
st.insert({d[it.first], it.first});↵
}↵
}↵
cout << d[0];↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:11,option1]↵
↵
Хорошая задача: [likes:11,option2]↵
↵
Нормальная задача: [likes:11,option3]↵
↵
Плохая задача: [likes:11,option4]↵
↵
Отвратительная задача: [likes:11,option5]↵
↵
Не решил: [likes:11,option6]↵
</spoiler>↵
↵
↵
[Задача A: Сергей и MEX](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/A)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Давайте заметим, что $a_i > 0$, поэтому $MEX(a_1, a_2, ..., a_n) = 0$. Значит если $k = a_i$ для какого то $i$, то это значит, что новый MEX будет больше 0. Значит надо вывести любое число, которого нету в массиве. ↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int int64_t↵
void sol() {↵
int n;↵
cin >> n;↵
int a[n];↵
for (int i=0;i<n;i++)↵
cin>>a[i];↵
if(n==3&&a[0]==1&&a[1]==2&&a[2]==3){↵
cout<<4;↵
return;↵
}↵
int r=1;↵
for(int w=0;w<31;w++) {↵
r*=2;↵
}↵
cout << r;↵
}↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
int t=1;↵
while (t--) {↵
sol();↵
}↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:1,option1]↵
↵
Хорошая задача: [likes:1,option2]↵
↵
Нормальная задача: [likes:1,option3]↵
↵
Плохая задача: [likes:1,option4]↵
↵
Отвратительная задача: [likes:1,option5]↵
↵
Не решил: [likes:1,option6]↵
</spoiler>↵
↵
[Задача B: Андрей и монстры](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/B)↵
↵
Автор: [user:onlytrall,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Во-первых, лекари не наносят никакого урона, поэтому их наличие никак не влияет на задачу.↵
↵
Давайте выпишем весь урон полученный Андреем:↵
$damage = 0 + k + 2 \cdot k + \dots + x \cdot k$, где $x$ максимальное, при котором выполняется $x \cdot k \le n$. Попробуем найти его. Это условие равносильно $x \le \dfrac{n}{k}$, значит $x = \lfloor{\dfrac{n}{k}} \rfloor$. Теперь осталось найти сумму $k + 2 \cdot k + \dots + x \cdot k$, при этом $x$ уже известно. Можно заметить, что все слагаемые кратны $k$, его можно вынести:↵
$damage = k \cdot (1 + 2 + 3 + \dots + x)$. Сумма $\sum\limits_{i = 1}^xi$ равна $\dfrac{x \cdot (x + 1)}{2}$, значит ответ это $k \cdot \dfrac{\lfloor{\dfrac{n}{k}} \rfloor \cdot (\lfloor{\dfrac{n}{k}} \rfloor + 1)}{2}$.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <iostream>↵
↵
using namespace std;↵
#define int int64_t↵
↵
void sol() {↵
int n, k;↵
cin >> n >> k;↵
int j = n / k;↵
cout << ((j * (j + 1)) / 2) * k << '\n';↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
int t = 1;↵
while (t--) {↵
sol();↵
}↵
}↵
↵
↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:2,option1]↵
↵
Хорошая задача: [likes:2,option2]↵
↵
Нормальная задача: [likes:2,option3]↵
↵
Плохая задача: [likes:2,option4]↵
↵
Отвратительная задача: [likes:2,option5]↵
↵
Не решил: [likes:2,option6]↵
</spoiler>↵
↵
[Задача C: Сергей и четыре числа](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/C)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Как известно, при $x \geq y$ выполняется $gcd(x, y) = gcd(x - y, y)$. <br>↵
<br>↵
Поэтому $gcd(a + 2b, a + b) = gcd(a + b, b) = gcd(a, b)$, а также $gcd(b + 4c, b + 3c) = gcd(b + 3c, c) = gcd(b, c)$<br>↵
Остается лишь найти такие различные $a, b, c$ такие, что $gcd(a, b) = gcd(b, c) = d$. Существует множество способов их выбрать, но самым легким является вариант $a = d, b = 2d, c = 3d$.<br>↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
#define int int64_t↵
↵
void sol() {↵
int d;↵
cin >> d;↵
if (d == 1)↵
cout << 998244353 << ' ' << 1000000007 << ' ' << 1000000009 << '\n';↵
else↵
cout << d << ' ' << 2 * d << ' ' << 3 * d << '\n';↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
sol();↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:3,option1]↵
↵
Хорошая задача: [likes:3,option2]↵
↵
Нормальная задача: [likes:3,option3]↵
↵
Плохая задача: [likes:3,option4]↵
↵
Отвратительная задача: [likes:3,option5]↵
↵
Не решил: [likes:3,option6]↵
</spoiler>↵
↵
[Автор D: Шахматная доска](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/D)↵
↵
Author: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Квадрат $2\times2$ мы можем покрасить $14-ю$ способами: $2^4 - 2$ ($2^4$ это количество способов раскрасить квадрат, 2 способа некорректны — когда мы красив весь квадрат либо в белый, либо в чёрный цвет). Всего таких квадратов $\frac {n^2}{4}$. Значит ответ равен $14^\frac {n^2}{4}$. Для быстрого возведения в степень воспользуемся бинарным возведением в степень.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <iostream>↵
#include <cmath>↵
using namespace std;↵
long long mod = 1e9 + 7;↵
↵
long long binpow(long long k) {↵
if (!k)↵
return 1;↵
if (k % 2)↵
return (binpow(k - 1) * (long long)14) % mod;↵
long long a = binpow(k / 2);↵
return (a * a) % mod;↵
}↵
↵
int main(int argc, char** argv) {↵
int t;↵
cin >> t;↵
while (t--) {↵
long long n;↵
cin >> n;↵
cout << binpow(n * n / 4) << '\n';↵
}↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:4,option1]↵
↵
Хорошая задача: [likes:4,option2]↵
↵
Нормальная задача: [likes:4,option3]↵
↵
Плохая задача: [likes:4,option4]↵
↵
Отвратительная задача: [likes:4,option5]↵
↵
Не решил: [likes:4,option6]↵
</spoiler>↵
↵
[Задача E: Сергей и массив](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/E)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
В задаче от нас требуется реализовать стек с поддержкой $gcd$<br>↵
<br>↵
Давайте научимся отвечать на каждый запрос за $\mathcal{O}(1)$↵
Для этого будем в стеке хранить пару чисел — сам элемент, а также $gcd$ элементов, лежащих в стеке не выше данного.↵
Иными словами:<br>↵
$stack_i.first = a_i$<br>↵
$stack_i.second = gcd(a_1, a_2, ..., a_i)$<br>↵
Тогда $gcd$ всего стека будет находиться в $stack.top().second$<br>↵
Чтобы выполнить запрос удаления, достаточно удалить верхний элемент стека, так как он не влияет на предыдущие элементы.<br>↵
Чтобы добавить элемент в стек, нам нужно добавить пару $element,\;gcd(stack.top().second, element)$ (нужно не забыть рассмотреть случай, когда стек пуст)<br></spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
typedef int ll;↵
typedef long double ld;↵
ll mod = 1e9 + 7;↵
ld eps = 1e-15;↵
↵
ll gcd(ll a, ll b) {↵
if (a < b)↵
swap(a, b);↵
if (a % b == 0)↵
return b;↵
return gcd(b, a % b);↵
}↵
↵
int main(int argc, char** argv) {↵
ll n, i;↵
cin >> n;↵
vector<ll> a(n), pr(n);↵
for (i = 0; i < n; i++) {↵
cin >> a[i];↵
if (!i)↵
pr[i] = a[i];↵
else↵
pr[i] = gcd(a[i], pr[i - 1]);↵
}↵
ll q;↵
cin >> q;↵
while (q--) {↵
ll t;↵
cin >> t;↵
if (!t)↵
pr.pop_back();↵
else {↵
ll x;↵
cin >> x;↵
if (pr.empty())↵
pr.push_back(x);↵
else↵
pr.push_back(gcd(x, pr.back()));↵
}↵
if (pr.empty())↵
cout << "1\n";↵
else↵
cout << pr.back() << '\n';↵
}↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:5,option1]↵
↵
Хорошая задача: [likes:5,option2]↵
↵
Нормальная задача: [likes:5,option3]↵
↵
Плохая задача: [likes:5,option4]↵
↵
Отвратительная задача: [likes:5,option5]↵
↵
Не решил: [likes:5,option6]↵
</spoiler>↵
↵
[Задача F1: Сергей и простые числа (простая версия)](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/F1)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Сначала рассмотрим $x\leq11$. Несложно убедиться, из них хорошими являются только $8$ и $10$. Далее рассматриваются $x>11$.↵
<br> Дальше заметим, что одно из чисел $x-4$, $x-6$, $x-8$ будет составным, потому что будет делиться на 3(но при этом не равно трем). Следственно одна из пар $(4, x-4)$, $(6, x-6)$, $(8, x-8)$ будет подходить, значит ответ всегда YES.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int int64_t↵
void sol() {↵
int x;↵
cin >> x;↵
if(x<=11) {↵
if(x==8 || x==10) {↵
cout << "YES";↵
}↵
else {↵
cout << "NO";↵
}↵
}↵
else {↵
cout << "YES";↵
}↵
cout << '\n';↵
}↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
//freopen ("commander.in", "rt", stdin);↵
//freopen ("commander.out", "wt", stdout);↵
int t=1;↵
cin >> t;↵
while(t--) {↵
sol();↵
}↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:6,option1]↵
↵
Хорошая задача: [likes:6,option2]↵
↵
Нормальная задача: [likes:6,option3]↵
↵
Плохая задача: [likes:6,option4]↵
↵
Отвратительная задача: [likes:6,option5]↵
↵
Не решил: [likes:6,option6]↵
</spoiler>↵
↵
[Задача F2: Сергей и простые числа (сложная версия)](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/F2)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Решение 1:↵
↵
Давайте применим бинарную теорему Гольдбаха(любое четное число начиная с 4 можно представить в виде суммы двух простых чисел). Тогда если 2 то ответ $NO$. Иначе $YES$. Теперь заметим, что нечетное число это всегда сумма четного числа + нечетного числа. Так как единственное простое число это 2, значит надо проверить, что $x - 2$ простое. ↵
↵
Решение 2: ↵
↵
Давайте посчитаем с помощью решета Эратосфена все простые числа до $10^{6}$. Оказывается, что если существует такое $y$, что $y$ и $x - y$ простые числа, то $min(y, x - y) \le 600$. Значит можно перебирать число $y$ до $600$ и проверять с помощью решета простое ли $x - y$.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int int64_t↵
void sol() {↵
int tests;↵
cin >> tests;↵
vector <bool> f(1000001, true);↵
f[1]=false;↵
for(int r=2;r<f.size();r++) {↵
if(f[r]) {↵
for(int w=r;w*r<f.size();w++) {↵
f[w*r]=false;↵
}↵
}↵
}↵
while(tests--) {↵
int y;↵
cin >> y;↵
if(y%2==0) {↵
if(y>=4) {↵
cout << "YES";↵
}↵
else {↵
cout << "NO";↵
}↵
}↵
else {↵
if(y<=3) {↵
cout << "NO";↵
}↵
else {↵
if(f[y-2]) {↵
cout << "YES";↵
}↵
else {↵
cout << "NO";↵
}↵
}↵
}↵
cout << '\n';↵
}↵
}↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
//freopen ("paths.in", "rt", stdin);↵
//freopen ("paths.out", "wt", stdout);↵
int t=1;↵
while(t--) {↵
sol();↵
}↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:7,option1]↵
↵
Хорошая задача: [likes:7,option2]↵
↵
Нормальная задача: [likes:7,option3]↵
↵
Плохая задача: [likes:7,option4]↵
↵
Отвратительная задача: [likes:7,option5]↵
↵
Не решил: [likes:7,option6]↵
</spoiler>↵
↵
[Задача G: Кирилл и вакцина](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/G)↵
↵
Автор: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Для начала заметим, что возможен такой жадный алгоритм: пока в первом городе остались зараженные жители, будем летать на отрезке городов с $1$ по $k$ (иначе мы никак не вылечим первый город). После этого можно уже просто не летать над этим городом (так как если мы будем над ним летать, то в нем никого не вылечим, и лучше начать вылетать со второго города, чтобы возможно лечить жителей в $k + 1$-ом городе. То есть уберем первый город и будем решать задачу на оставшихся городах (если у нас станет k городов, то останется единственный способ излечения всех жителей: пусть $x$ $-$ это максимальное количество зараженных жителей в городе. Тогда к ответу надо прибавить $\lceil{\frac{x}{k}}\rceil$.↵
↵
Осталось только быстро обновлять количество зараженных жителей в городах с $l$-го по $l + k - 1$-ый (когда мы пролетаем над этими городами). Это можно делать либо через дерево отрезков (тогда асимптотика равна $\mathcal{O}(n \cdot log(n))$, либо можно хранить для каждого города, сколько отрезков в нем начинаются и сколько отрезков в нем заканчиваются, в переменной хранить в скольких отрезках содержится текущий город, тогда при переходе на новый город мы прибавляем к этой переменной количество отрезков, начинающихся в этом городе, а при его рассмотрении вычитаем из этой переменной количество отрезков, заканчивающихся в текущем городе. Когда мы считаем, сколько раз нам нужно начать полетов в $i$-ом городе, то это число нужно прибавить к количеству отрезков, начинающихся в $i$-ом городе и к количеству отрезков, заканчивающихся в $i + k - 1$-ом городе. Тогда асимптотика будет равна $\mathcal{O}(n)$.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
//#pragma optimize("3,o3,ofast")↵
↵
#include <iostream>↵
#include <vector>↵
#include <set>↵
#include <map>↵
#include <queue>↵
#include <cassert>↵
#include <iomanip>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef double ld;↵
//typedef __int128 lll;↵
ll inf = 1e15, mod = 998244353;↵
ld eps = 1e-6;↵
#define all(a) a.begin(), a.end()↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
ll n, k, x, i;↵
cin >> n >> k >> x;↵
vector<ll> a(n), upd(n);↵
for (i = 0; i < n; i++)↵
cin >> a[i];↵
ll ans = 0, sm = 0;↵
for (i = 0; i < n; i++) {↵
sm -= upd[i];↵
a[i] -= sm;↵
if (a[i] > 0) {↵
sm += (a[i] + x - 1) / x * x;↵
ans += (a[i] + x - 1) / x;↵
if (i + k < n)↵
upd[i + k] = (a[i] + x - 1) / x * x;↵
}↵
}↵
cout << ans;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:8,option1]↵
↵
Хорошая задача: [likes:8,option2]↵
↵
Нормальная задача: [likes:8,option3]↵
↵
Плохая задача: [likes:8,option4]↵
↵
Отвратительная задача: [likes:8,option5]↵
↵
Не решил: [likes:8,option6]↵
</spoiler>↵
↵
[Задача H: Кирилл и НОД](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/H)↵
↵
Автор: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Для начала заметим, что если $gcd(x, y) > 1$, то $gcd(x \cdot k, y) > 1$ для любого натурального $k$. Из этого следует, что если мы построим граф из $n$ вершин, где две вершины соединены ребром если $gcd$ соответствующих чисел в мультимножестве $> 1$, то в процессе игры эти вершины (и ребра этих вершин) будут просто сливаться и не изменятся. Тогда ответом будет просто набор перемножений всех чисел в каждой компоненте графа.↵
↵
Нам нужно научиться быстро строить граф. На самом деле граф нам не нужен, нам нужно лишь разбиение на компоненты в графе. Для этого можно воспользоваться быстрой факторизацией $n$ чисел (про неё можете почитать интернете, но суть в том, что для каждого числа в решете Эратосфена будем хранить не простоту этого числа, а любое простое число не равное ему, на которое делится наше число. Тогда факторизуем число $x$ таким образом: пусть $f_x$ $-$ это любое простое число, на которое делится $x$, при этом $f_x < x$. Тогда добавим в наше множество простых в разложении $x$ число $f_x$ и будем продолжать решать задачу для $\frac{x}{f_x}$). Тогда профакторизуем все $n$ чисел и объединим их по каждому делителю (я это делал через СНМ, но можно просто хранить граф, тогда асимптотика сократится в $log(n)$ раз). Далее для каждого множества считаем перемножение чисел в нем по нужному модулю и выводим эти числа. Асимтотика авторского решения $\mathcal{O}(10^7 \cdot log(10^7) + n \cdot log(n))$.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
~~~~~↵
#include <iostream>↵
#include <fstream>↵
#include <iomanip>↵
#include <vector>↵
#include <algorithm>↵
#include <string>↵
#include <set>↵
#include <cmath>↵
#include <deque>↵
#include <map>↵
#include <cassert>↵
#include <queue>↵
#include <unordered_set>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef __int128 lll;↵
typedef long double ld;↵
const ll mod = 1e9 + 7, inf = 2e18 + 1;↵
const ld eps = 1e-9, pi = 3.1415926;↵
#define all(a) a.begin(), a.end()↵
↵
ll gcd(ll a, ll b) {↵
if (a < b)↵
swap(a, b);↵
if (!b)↵
return a;↵
return gcd(b, a % b);↵
}↵
↵
vector<ll> tr;↵
↵
ll root(ll v) {↵
if (tr[v] == v)↵
return v;↵
return tr[v] = root(tr[v]);↵
}↵
↵
void unite(ll a, ll b) {↵
a = root(a);↵
b = root(b);↵
tr[b] = a;↵
}↵
↵
int main() {↵
//ios_base::sync_with_stdio(false);↵
//ifstream cin("line3.in");↵
//ofstream cout("line3.out");↵
//cin.tie(nullptr);↵
//cout.tie(nullptr);↵
//in.tie(nullptr);↵
//out.tie(nullptr);↵
ll n, i;↵
cin >> n;↵
tr.resize(n);↵
for (i = 0; i < n; i++)↵
tr[i] = i;↵
vector<ll> u(1e7 + 1);↵
for (i = 2; i <= 1e7; i++)↵
if (!u[i]) {↵
u[i] = i;↵
for (ll j = i * i; j <= 1e7; j += i)↵
u[j] = i;↵
}↵
vector<ll> a(n);↵
for (i = 0; i < n; i++)↵
cin >> a[i];↵
auto b = a;↵
map<ll, vector<ll>> mp;↵
for (i = 0; i < n; i++)↵
while (a[i] > 1) {↵
ll x = u[a[i]];↵
mp[x].push_back(i);↵
while (a[i] % x == 0)↵
a[i] /= x;↵
}↵
for (auto it:mp) {↵
ll x = it.second[0];↵
for (i = 1; i < it.second.size(); i++)↵
unite(x, it.second[i]);↵
}↵
a = b;↵
map<ll, ll> mp1;↵
for (i = 0; i < n; i++) {↵
tr[i] = root(i);↵
if (!mp1[tr[i]])↵
mp1[tr[i]] = 1;↵
mp1[tr[i]] = (mp1[tr[i]] * a[i]) % mod;↵
}↵
cout << mp1.size() << '\n';↵
for (auto it:mp1)↵
cout << it.second << ' ';↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:9,option1]↵
↵
Хорошая задача: [likes:9,option2]↵
↵
Нормальная задача: [likes:9,option3]↵
↵
Плохая задача: [likes:9,option4]↵
↵
Отвратительная задача: [likes:9,option5]↵
↵
Не решил: [likes:9,option6]↵
</spoiler>↵
↵
[Задача I: Сергей и НОД](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/I)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
Будем искать количество $r$ для каждого $l$ отдельно. <br>↵
<br>↵
Давайте пока забудем про условие $gcd(a_l, a_r)>1$. Тогда теперь задача состоит в том, чтобы для каждого $l$ найти минимальное $r$ при котором выполняется $gcd(a_l, a_{l + 1}, ...,a_r) = 1$. Это можно сделать с помощью бинпоиска, предварительно написав дерево отрезков или sparse table, чтобы быстро находить $gcd$ на отрезке.<br>↵
<br>↵
Мы научились для каждого $l$ находить суффикс, на котором мы можем выбирать $r$. Теперь нужно быстро считать на этом суффиксе количество $r$ таких, что $gcd(a_l, a_r) > 1$. Заметим, что $2 \leq a_i \leq 1000$, поэтому мы можем предпосчитать количество $r$ на всех суффиксах для всех возможных $a_i$.<br>↵
Пусть $dp[x][i]$ — количество чисел на суффиксе $a_i, a_{i + 1}, ..., a_{n - 1}$ не взаимно простых с x. В качестве базы динамики сделаем $dp[x][n] = 0$. Пересчитывается динамика просто — $dp[x][i] = dp[x][i + 1] + (gcd(x, a_i) > 1)$. Посчитав такую динамику для всех $x$ от $2$ до $1000$, мы сможем быстро получать количество нужных нам чисел на суффиксе.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int int64_t↵
vector<int> a(50001,0);↵
vector<int> tr(200002,0);↵
int gcd(int b, int c) {↵
if(b<c) {↵
swap(b,c);↵
}↵
if(c==0) {↵
return b;↵
}↵
else {↵
return gcd(c, b%c);↵
}↵
}↵
void bul(int u, int l, int r) {↵
if (l == r) {↵
tr[u] = a[l];↵
} else {↵
bul(u * 2, l, (l + r) / 2);↵
bul(u * 2 + 1, (l + r) / 2 + 1, r);↵
tr[u] = gcd(tr[u * 2], tr[u * 2 + 1]);↵
}↵
}↵
↵
int gcd(int u, int l, int r, int l2, int r2) {↵
if (l <= l2 && r2 <= r) {↵
return tr[u];↵
}↵
if (r2 < l || l2 > r) {↵
return 0;↵
}↵
return gcd(gcd(u * 2, l, r, l2, (l2 + r2) / 2), gcd(u * 2 + 1, l, r, (l2 + r2) / 2 + 1, r2));↵
}↵
bool f[1001][1001];↵
int dp[50005][1001];↵
void sol() {↵
int n;↵
cin >> n;↵
for (int r = 0; r < n; r++) {↵
cin >> a[r];↵
}↵
for (int r = 1; r <= 1000; r++) {↵
for (int w = 1; w <= 1000; w++) {↵
if (gcd(r, w) > 1) {↵
f[r][w] = true;↵
} else {↵
f[r][w] = false;↵
}↵
}↵
}↵
for (int r = n - 1; r >= 0; r--) {↵
for (int w = 1; w <= 1000; w++) {↵
if (r == n - 1) {↵
if (f[w][a[r]]) {↵
dp[r][w] = 1;↵
} else {↵
dp[r][w] = 0;↵
}↵
} else {↵
dp[r][w] = dp[r + 1][w];↵
if (f[w][a[r]]) {↵
dp[r][w]++;↵
}↵
}↵
}↵
}↵
int sum = 0;↵
bul(1, 0, n - 1);↵
for (int r = 0; r < n; r++) {↵
int l = r, w = n;↵
while (l + 1 < w) {↵
int u = (l + w)/2;↵
if (gcd(1, r, u, 0, n - 1) == 1) {↵
w = u;↵
} else {↵
l = u;↵
}↵
}↵
if (l != n - 1) {↵
sum += dp[l + 1][a[r]];↵
}↵
}↵
cout << sum;↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
int t = 1;↵
while (t--) {↵
sol();↵
}↵
}//↵
↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:10,option1]↵
↵
Хорошая задача: [likes:10,option2]↵
↵
Нормальная задача: [likes:10,option3]↵
↵
Плохая задача: [likes:10,option4]↵
↵
Отвратительная задача: [likes:10,option5]↵
↵
Не решил: [likes:10,option6]↵
</spoiler>↵
↵
[Задача J: Кирилл и путешествие](https://mirror.codeforces.com/group/cBrcov20zj/contest/382218/problem/J)↵
↵
Автор: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Разбор">↵
1 решение:↵
↵
Будем искать ответ с конца, предполагая, что по приезде в вершину n останется ровно $t$ монет. Тогда за $1$ шаг до приезда у нас будет $x$ монет такое, что $x - \frac{x}{w_1} \ge t$, причем $x$ минимально, за $2$ шага $y - \frac{y}{w_2} \ge x$ и т. д., где $w_1$ и $w_2$ $-$ веса дорог из оптимального пути. Пусть $d_i$ $-$ минимальное число монет, которое будет когда мы попадем из $n$ в $i$, тогда можно легко восстановить все веса ребер из $i$ в соответствии с неравенством выше. Теперь задача свелась к тому что надо найти кратчайший путь из $n$ в $1$. Для этого можно воспользоваться алгоритмом Дейкстры (он работает, так как ребра не изменяются случайно, и отрицательных ребер нет).↵
↵
2 решение:↵
↵
Будем бинпоиском перебирать ответ: тогда для каждого возможного ответа сделаем обычную Дейкстру (просто веса будут изменятся в зависимости от кратчайшего пути в вершину). Проверяем что расстояние то вершины $n$ больше или равно $t$.↵
↵
В обоих решениях асимптотика $\mathcal{O}(n \cdot log(n) \cdot log(10^9))$.↵
↵
В коде написано первое решение.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <iostream>↵
#include <fstream>↵
#include <iomanip>↵
#include <vector>↵
#include <algorithm>↵
#include <string>↵
#include <set>↵
#include <cmath>↵
#include <deque>↵
#include <map>↵
#include <cassert>↵
#include <queue>↵
#include <unordered_set>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef __int128 lll;↵
typedef long double ld;↵
const ll mod = 1e9 + 7, inf = 2e18 + 1;↵
const ld eps = 1e-9, pi = 3.1415926;↵
#define all(a) a.begin(), (a).end()↵
↵
ll f(ll d, ll w) {↵
if (d < w)↵
return d;↵
ll l = 0, r = 1000000001, md;↵
while (l + 1 < r) {↵
md = (l + r) / 2;↵
if (md - md / w >= d)↵
r = md;↵
else↵
l = md;↵
}↵
return r;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
//ifstream cin("line3.in");↵
//ofstream cout("line3.out");↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
//in.tie(nullptr);↵
//out.tie(nullptr);↵
ll n, m, t, i;↵
cin >> n >> m >> t;↵
vector<vector<pair<ll, ll>>> g(n);↵
while (m--) {↵
ll u, v, w;↵
cin >> u >> v >> w;↵
u--;↵
v--;↵
g[u].push_back({v, w});↵
g[v].push_back({u, w});↵
}↵
vector<ll> d(n, inf);↵
d[n - 1] = t;↵
set<pair<ll, ll>> st;↵
st.insert({t, n - 1});↵
while (!st.empty()) {↵
ll v = st.begin()->second;↵
st.erase(st.begin());↵
for (auto it:g[v])↵
if (d[it.first] > f(d[v], it.second)) {↵
st.erase({d[it.first], it.first});↵
d[it.first] = f(d[v], it.second);↵
st.insert({d[it.first], it.first});↵
}↵
}↵
cout << d[0];↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Фидбек">↵
Отличная задача: [likes:11,option1]↵
↵
Хорошая задача: [likes:11,option2]↵
↵
Нормальная задача: [likes:11,option3]↵
↵
Плохая задача: [likes:11,option4]↵
↵
Отвратительная задача: [likes:11,option5]↵
↵
Не решил: [likes:11,option6]↵
</spoiler>↵
↵
