If you have a solution other than the author's, write it in the comments. There is an assessment under each solution, please rate all the tasks. Contest: [Contest](https://codeforces.me/group/cBrcov20zj/contest/382218).↵
↵
[Problem A: Sergey and MEX](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/A)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
Let's note that $a_i > 0$, so $MEX(a_1, a_2, ..., a_n) = 0$. So if $k=a_i$ for some $i$, it means that the new MEX will be greater than 0. So you need to output any number that is not in the array.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great task: [likes:1,option1]↵
↵
Good task: [likes:1,option2]↵
↵
Normal task: [likes:1,option3]↵
↵
Bad task: [likes:1,option4]↵
↵
Disgusting task: [likes:1,option5]↵
↵
Not solved: [likes:1,option6]↵
</spoiler>↵
↵
[Task B: Andrey and the monsters](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/B )↵
↵
Author: [user:onlytrall,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
Firstly, healers do not cause any damage, so their presence does not affect the task in any way.↵
↵
Let's write out all the damage received by Andrey:↵
$damage = 0 + k + 2 \cdot k + \dots + x \cdot k$, where $x$ is the maximum at which $x \cdot k\le n$ is executed. Let's try to find him. This condition is equivalent to $x\le\dfrac{n}{k}$, so $x =\lfloor{\dfrac{n}{k}}\rfloor$. Now it remains to find the sum of $k + 2 \cdot k + \dots + x \cdot k$, while $x$ is already known. It can be noticed that all terms are multiples of $k$, it can be taken out:↵
$damage = k \cdot (1 + 2 + 3 + \dots + x)$. The sum of $\sum\limits_{i = 1}^xi$ is equal to $\dfrac{x\cdot (x + 1)}{2}$, so the answer is $k\cdot\dfrac{\lfloor{\dfrac{n}{k}} \rfloor\cdot (\lfloor{\dfrac{n}{k}}\rfloor+1)}{2}$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:2,option1]↵
↵
Good task: [likes:2,option2]↵
↵
Normal task: [likes:2,option3]↵
↵
Bad task: [likes:2,option4]↵
↵
Disgusting task: [likes:2,option5]↵
↵
Not solved: [likes:2,option6]↵
</spoiler>↵
↵
[Task C: Sergey and four numbers](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/C )↵
↵
Author: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
As is known, for $x\geq y$, $gcd(x, y) = gcd(x - y, y)$ is executed. <br>↵
<br>↵
Therefore $gcd(a + 2b, a + b) = gcd(a + b, b) = gcd(a, b)$, and $gcd(b + 4c, b + 3c) = gcd(b + 3c, c) = gcd(b, c)$<br>↵
It remains only to find such different $a, b, c$ such that $gcd(a, b) = gcd(b, c) = d$. There are many ways to choose them, but the easiest option is $a = d, b = 2d, c = 3d$.<br>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:3,option1]↵
↵
Good task: [likes:3,option2]↵
↵
Normal task: [likes:3,option3]↵
↵
Bad task: [likes:3,option4]↵
↵
Disgusting task: [likes:3,option5]↵
↵
Not solved: [likes:3,option6]↵
</spoiler>↵
↵
[Author D: Chessboard](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/D )↵
↵
Author: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
Square $2\times2$ we can color $14$ in ways: $2^4 - 2$ ($2^4$ this is the number of ways to color a square, 2 ways are incorrect when we turn the whole square either white or black). There are total of such squares $\frac{n^2}{4}$. So the answer is $14^\frac{n^2}{4}$. For a quick exponentiation, we use binary exponentiation.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:4,option1]↵
↵
Good task: [likes:4,option2]↵
↵
Normal task: [likes:4,option3]↵
↵
Bad task: [likes:4,option4]↵
↵
Disgusting task: [likes:4,option5]↵
↵
Not solved: [likes:4,option6]↵
</spoiler>↵
↵
[Task E: Sergey and the array](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/E )↵
↵
Author: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
In the task, we are required to implement a stack with support for $gcd$<br>↵
<br>↵
Let's learn how to answer each query for $\mathcal{O}(1)$↵
To do this, we will store a pair of numbers in the stack — the element itself, as well as $gcd$ elements lying in the stack no higher than this.↵
In other words:<br>↵
$stack_i.first = a_i$<br>↵
$stack_i.second = gcd(a_1, a_2, ..., a_i)$<br>↵
Then $gcd$ of the entire stack will be in $stack.top().second$<br>↵
To make a deletion request, it is enough to delete the top element of the stack, since it does not affect the previous elements.<br>↵
To add an element to the stack, we need to add a pair of $element,\;gcd(stack.top().second, element)$ (we must not forget to consider the case when the stack is empty)<br></spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:5,option1]↵
↵
Good task: [likes:5,option2]↵
↵
Normal task: [likes:5,option3]↵
↵
Bad task: [likes:5,option4]↵
↵
Disgusting task: [likes:5,option5]↵
↵
Didn't decide: [likes:5,option6]↵
</spoiler>↵
↵
[F1 Problem: Sergey and prime numbers (simple version)](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/F1)↵
↵
Author: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
First consider $x \le 11$. It's easy to make sure that only $8$ and $10$ are good ones. Next, $x>11$ are considered.↵
<br> Next, we note that one of the numbers $x-4$, $x-6$, $x-8$ will be composite, because it will be divisible by 3 (but not equal to three). Consequently, one of the pairs $(4, x-4)$, $(6, x-6)$, $(8, x-8)$ will fit, so the answer is always YES.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:6,option1]↵
↵
Good task: [likes:6,option2]↵
↵
Normal task: [likes:6,option3]↵
↵
Bad task: [likes:6,option4]↵
↵
Disgusting task: [likes:6,option5]↵
↵
Didn't decide: [likes:6,option6]↵
</spoiler>↵
↵
[Task F2: Sergey and prime numbers (complex version)](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/F2)↵
↵
Author: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
Solution 1:↵
↵
Let's apply Goldbach's binary theorem (any even number starting from 4 can be represented as the sum of two primes). Then if 2 then the answer is $NO$. Otherwise, $YES$. Now note that an odd number is always the sum of an even number + an odd number. Since the only prime number is 2, it means we need to check that $x-2$ is prime. ↵
↵
Solution 2: ↵
↵
Let's use the Eratosthenes sieve to calculate all the primes up to $10^{6}$. It turns out that if there is such a $y$ that $y$ and $x - y$ are prime numbers, then $min(y, x - y) \le 600$. So you can iterate over the number y up to 600 and check with a sieve whether $x - y$ is simple.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:7,option1]↵
↵
Good task: [likes:7,option2]↵
↵
Normal task: [likes:7,option3]↵
↵
Bad task: [likes:7,option4]↵
↵
Disgusting task: [likes:7,option5]↵
↵
Not solved: [likes:7,option6]↵
</spoiler>↵
↵
[Task G: Kirill and the vaccine](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/G )↵
↵
Author: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
To begin with, we note that such a greedy algorithm is possible: while there are infected residents in the first city, we will fly on a segment of cities from $1$ to $k$ (otherwise we will not cure the first city in any way). After that, you can simply not fly over this city (since if we fly over it, we will not cure anyone in it, and it is better to start flying from the second city so that it is possible to treat residents in the $k + 1$ city. That is, we will remove the first city and solve the problem on the remaining cities (if we have k cities, then there will be only one way to cure all residents: let $x$ $-$ be the maximum number of infected residents in the city. Then add $\lceil{\frac{x}{k}}\rceil$ to the answer.↵
↵
It remains only to quickly update the number of infected residents in cities from $l$ to $l + k - 1$ (when we fly over these cities). This can be done either through a tree of segments (then the asymptotics is $\mathcal{O}(n \cdot log(n))$, or you can store for each city how many segments begin in it and how many segments end in it, in the variable store how many segments contain the current city, then when switching to we add to this variable the number of segments starting in this city, and when considering it, we subtract from this variable the number of segments ending in the current city. When we count how many times we need to start flights in the $i$th city, then this number must be added to the number of segments starting in the $i$th city and to the number of segments ending in the $i + k - 1$th city. Then the asymptotics will be equal to $\mathcal{O}(n)$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
//#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="Feedback">↵
Great challenge: [likes:8,option1]↵
↵
Good task: [likes:8,option2]↵
↵
Normal task: [likes:8,option3]↵
↵
Bad task: [likes:8,option4]↵
↵
Disgusting task: [likes:8,option5]↵
↵
Not solved: [likes:8,option6]↵
</spoiler>↵
↵
[Task H: Kiril and NODE](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/H )↵
↵
Author: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
To begin with, note that if $gcd(x, y) > 1$, then $gcd(x \cdot k, y) > 1$ for any natural $k$. It follows from this that if we build a graph of $n$ vertices, where two vertices are connected by an edge if $gcd$ of the corresponding numbers in the multiset $> 1$, then during the game these vertices (and the edges of these vertices) will simply merge and will not change. Then the answer will simply be a set of multiplications of all the numbers in each component of the graph.↵
↵
We need to learn how to build a graph quickly. In fact, we don't need a graph, we just need a partition into components in the graph. To do this, you can use the fast factorization of $n$ numbers (you can read about it on the Internet, but the bottom line is that for each number in the sieve of Eratosthenes, we will not store the simplicity of this number, but any prime number not equal to it, by which our number is divided. Then factorize the number $x$ in this way: let $f_x$$-$ be any prime number by which $x$ is divisible, while $f_x < x$. Then we add the number $f_x$ to our set of easy-to-decompose $x$ and we will continue to solve the problem for $\frac{x}{f_x}$). Then we will profactorize all $n$ numbers and combine them for each divisor (I did it through the SNM, but you can just store the graph, then the asymptotics will be reduced by $log(n)$ times). Next, for each set, we calculate the multiplication of the numbers in it by the desired modulus and output these numbers. The asymptotics of the author's solution $\mathcal{O}(10^7 \cdot log(10^7) + n \cdot log(n))$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:9,option1]↵
↵
Good task: [likes:9,option2]↵
↵
Normal task: [likes:9,option3]↵
↵
Bad task: [likes:9,option4]↵
↵
Disgusting task: [likes:9,option5]↵
↵
Didn't decide: [likes:9,option6]↵
</spoiler>↵
↵
[Task I: Sergey and GCD] (https://codeforces.me/group/cBrcov20zj/contest/382218/problem/I )↵
↵
Author: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
We will search for the number of $r$ for each $l$ separately. <br>↵
<br>↵
Let's forget about the condition $gcd(a_l, a_r) >1$ for now. Then now the task is to find for each $l$ the minimum $r$ at which $gcd(a_l, a_{l + 1}, ...,a_r) = 1$ is executed. This can be done using bin-search, having previously written a tree of segments or sparse table to quickly find $gcd$ on a segment.<br>↵
<br>↵
We have learned to find a suffix for each $l$ on which we can choose $r$. Now we need to quickly count on this suffix the number of $r$ such that $gcd(a_l, a_r) > 1$. Note that $2\le a_i\le 1000$, so we can calculate the number of $r$ on all suffixes for all possible $a_i$.<br>↵
Let $dp[x][i]$ be the number of numbers on the suffix $a_i, a_{i + 1}, ..., a_{n - 1}$ that are not mutually prime with x. As a base of dynamics, we will make $dp[x][n] = 0$. The dynamics is recalculated simply — $dp[x][i] = dp[x][i + 1] + (gcd(x, a_i) > 1)$. By calculating such dynamics for all $x$ from $2$ to $1000$, we will be able to quickly get the number of numbers we need on the suffix.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:10,option1]↵
↵
Good task: [likes:10,option2]↵
↵
Normal task: [likes:10,option3]↵
↵
Bad task: [likes:10,option4]↵
↵
Disgusting task: [likes:10,option5]↵
↵
Not solved: [likes:10,option6]↵
</spoiler>↵
↵
[Task J: Kiril and the Journey](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/J )↵
↵
Author: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
1 solution:↵
↵
We will look for the answer from the end, assuming that upon arrival at the vertex n there will be exactly $t$ coins left. Then for $1$ step before arrival we will have $x$ coins such that $x - \frac{x}{w_1} \ge t$, and $x$ is minimal, for $2$ steps $y - \frac{y}{w_2} \ge x$, etc., where $w_1$ and $w_2$ are the weights of the roads from the optimal path. Let $d_i$ be the minimum number of coins that will be when we get from $n$ to $i$, then we can easily restore all the edge weights from $i$ in accordance with the inequality above. Now the task has been reduced to finding the shortest path from $n$ to $1$. To do this, you can use Dijkstra's algorithm (it works because the edges do not change randomly, and there are no negative edges).↵
↵
2 solution:↵
↵
We will search through the answer by bin-search: then we will make a regular Dijkstra for each possible answer (just the weights will change depending on the shortest path to the vertex). We check that the distance of the vertex $n$ is greater than or equal to $t$.↵
↵
In both solutions, the asymptotics of $\mathcal{O}(n \cdot log(n) \cdot log(10^9))$.↵
↵
The first solution is written in the code.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:11,option1]↵
↵
Good task: [likes:11,option2]↵
↵
Normal task: [likes:11,option3]↵
↵
Bad task: [likes:11,option4]↵
↵
Disgusting task: [likes:11,option5]↵
↵
Not solved: [likes:11,option6]↵
</spoiler>↵
↵
↵
[Problem A: Sergey and MEX](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/A)↵
↵
Автор: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
Let's note that $a_i > 0$, so $MEX(a_1, a_2, ..., a_n) = 0$. So if $k=a_i$ for some $i$, it means that the new MEX will be greater than 0. So you need to output any number that is not in the array.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great task: [likes:1,option1]↵
↵
Good task: [likes:1,option2]↵
↵
Normal task: [likes:1,option3]↵
↵
Bad task: [likes:1,option4]↵
↵
Disgusting task: [likes:1,option5]↵
↵
Not solved: [likes:1,option6]↵
</spoiler>↵
↵
[Task B: Andrey and the monsters](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/B )↵
↵
Author: [user:onlytrall,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
Firstly, healers do not cause any damage, so their presence does not affect the task in any way.↵
↵
Let's write out all the damage received by Andrey:↵
$damage = 0 + k + 2 \cdot k + \dots + x \cdot k$, where $x$ is the maximum at which $x \cdot k\le n$ is executed. Let's try to find him. This condition is equivalent to $x\le\dfrac{n}{k}$, so $x =\lfloor{\dfrac{n}{k}}\rfloor$. Now it remains to find the sum of $k + 2 \cdot k + \dots + x \cdot k$, while $x$ is already known. It can be noticed that all terms are multiples of $k$, it can be taken out:↵
$damage = k \cdot (1 + 2 + 3 + \dots + x)$. The sum of $\sum\limits_{i = 1}^xi$ is equal to $\dfrac{x\cdot (x + 1)}{2}$, so the answer is $k\cdot\dfrac{\lfloor{\dfrac{n}{k}} \rfloor\cdot (\lfloor{\dfrac{n}{k}}\rfloor+1)}{2}$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:2,option1]↵
↵
Good task: [likes:2,option2]↵
↵
Normal task: [likes:2,option3]↵
↵
Bad task: [likes:2,option4]↵
↵
Disgusting task: [likes:2,option5]↵
↵
Not solved: [likes:2,option6]↵
</spoiler>↵
↵
[Task C: Sergey and four numbers](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/C )↵
↵
Author: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
As is known, for $x\geq y$, $gcd(x, y) = gcd(x - y, y)$ is executed. <br>↵
<br>↵
Therefore $gcd(a + 2b, a + b) = gcd(a + b, b) = gcd(a, b)$, and $gcd(b + 4c, b + 3c) = gcd(b + 3c, c) = gcd(b, c)$<br>↵
It remains only to find such different $a, b, c$ such that $gcd(a, b) = gcd(b, c) = d$. There are many ways to choose them, but the easiest option is $a = d, b = 2d, c = 3d$.<br>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:3,option1]↵
↵
Good task: [likes:3,option2]↵
↵
Normal task: [likes:3,option3]↵
↵
Bad task: [likes:3,option4]↵
↵
Disgusting task: [likes:3,option5]↵
↵
Not solved: [likes:3,option6]↵
</spoiler>↵
↵
[Author D: Chessboard](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/D )↵
↵
Author: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
Square $2\times2$ we can color $14$ in ways: $2^4 - 2$ ($2^4$ this is the number of ways to color a square, 2 ways are incorrect when we turn the whole square either white or black). There are total of such squares $\frac{n^2}{4}$. So the answer is $14^\frac{n^2}{4}$. For a quick exponentiation, we use binary exponentiation.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:4,option1]↵
↵
Good task: [likes:4,option2]↵
↵
Normal task: [likes:4,option3]↵
↵
Bad task: [likes:4,option4]↵
↵
Disgusting task: [likes:4,option5]↵
↵
Not solved: [likes:4,option6]↵
</spoiler>↵
↵
[Task E: Sergey and the array](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/E )↵
↵
Author: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
In the task, we are required to implement a stack with support for $gcd$<br>↵
<br>↵
Let's learn how to answer each query for $\mathcal{O}(1)$↵
To do this, we will store a pair of numbers in the stack — the element itself, as well as $gcd$ elements lying in the stack no higher than this.↵
In other words:<br>↵
$stack_i.first = a_i$<br>↵
$stack_i.second = gcd(a_1, a_2, ..., a_i)$<br>↵
Then $gcd$ of the entire stack will be in $stack.top().second$<br>↵
To make a deletion request, it is enough to delete the top element of the stack, since it does not affect the previous elements.<br>↵
To add an element to the stack, we need to add a pair of $element,\;gcd(stack.top().second, element)$ (we must not forget to consider the case when the stack is empty)<br></spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:5,option1]↵
↵
Good task: [likes:5,option2]↵
↵
Normal task: [likes:5,option3]↵
↵
Bad task: [likes:5,option4]↵
↵
Disgusting task: [likes:5,option5]↵
↵
Didn't decide: [likes:5,option6]↵
</spoiler>↵
↵
[F1 Problem: Sergey and prime numbers (simple version)](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/F1)↵
↵
Author: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
First consider $x \le 11$. It's easy to make sure that only $8$ and $10$ are good ones. Next, $x>11$ are considered.↵
<br> Next, we note that one of the numbers $x-4$, $x-6$, $x-8$ will be composite, because it will be divisible by 3 (but not equal to three). Consequently, one of the pairs $(4, x-4)$, $(6, x-6)$, $(8, x-8)$ will fit, so the answer is always YES.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:6,option1]↵
↵
Good task: [likes:6,option2]↵
↵
Normal task: [likes:6,option3]↵
↵
Bad task: [likes:6,option4]↵
↵
Disgusting task: [likes:6,option5]↵
↵
Didn't decide: [likes:6,option6]↵
</spoiler>↵
↵
[Task F2: Sergey and prime numbers (complex version)](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/F2)↵
↵
Author: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
Solution 1:↵
↵
Let's apply Goldbach's binary theorem (any even number starting from 4 can be represented as the sum of two primes). Then if 2 then the answer is $NO$. Otherwise, $YES$. Now note that an odd number is always the sum of an even number + an odd number. Since the only prime number is 2, it means we need to check that $x-2$ is prime. ↵
↵
Solution 2: ↵
↵
Let's use the Eratosthenes sieve to calculate all the primes up to $10^{6}$. It turns out that if there is such a $y$ that $y$ and $x - y$ are prime numbers, then $min(y, x - y) \le 600$. So you can iterate over the number y up to 600 and check with a sieve whether $x - y$ is simple.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:7,option1]↵
↵
Good task: [likes:7,option2]↵
↵
Normal task: [likes:7,option3]↵
↵
Bad task: [likes:7,option4]↵
↵
Disgusting task: [likes:7,option5]↵
↵
Not solved: [likes:7,option6]↵
</spoiler>↵
↵
[Task G: Kirill and the vaccine](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/G )↵
↵
Author: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
To begin with, we note that such a greedy algorithm is possible: while there are infected residents in the first city, we will fly on a segment of cities from $1$ to $k$ (otherwise we will not cure the first city in any way). After that, you can simply not fly over this city (since if we fly over it, we will not cure anyone in it, and it is better to start flying from the second city so that it is possible to treat residents in the $k + 1$ city. That is, we will remove the first city and solve the problem on the remaining cities (if we have k cities, then there will be only one way to cure all residents: let $x$ $-$ be the maximum number of infected residents in the city. Then add $\lceil{\frac{x}{k}}\rceil$ to the answer.↵
↵
It remains only to quickly update the number of infected residents in cities from $l$ to $l + k - 1$ (when we fly over these cities). This can be done either through a tree of segments (then the asymptotics is $\mathcal{O}(n \cdot log(n))$, or you can store for each city how many segments begin in it and how many segments end in it, in the variable store how many segments contain the current city, then when switching to we add to this variable the number of segments starting in this city, and when considering it, we subtract from this variable the number of segments ending in the current city. When we count how many times we need to start flights in the $i$th city, then this number must be added to the number of segments starting in the $i$th city and to the number of segments ending in the $i + k - 1$th city. Then the asymptotics will be equal to $\mathcal{O}(n)$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
//#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="Feedback">↵
Great challenge: [likes:8,option1]↵
↵
Good task: [likes:8,option2]↵
↵
Normal task: [likes:8,option3]↵
↵
Bad task: [likes:8,option4]↵
↵
Disgusting task: [likes:8,option5]↵
↵
Not solved: [likes:8,option6]↵
</spoiler>↵
↵
[Task H: Kiril and NODE](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/H )↵
↵
Author: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
To begin with, note that if $gcd(x, y) > 1$, then $gcd(x \cdot k, y) > 1$ for any natural $k$. It follows from this that if we build a graph of $n$ vertices, where two vertices are connected by an edge if $gcd$ of the corresponding numbers in the multiset $> 1$, then during the game these vertices (and the edges of these vertices) will simply merge and will not change. Then the answer will simply be a set of multiplications of all the numbers in each component of the graph.↵
↵
We need to learn how to build a graph quickly. In fact, we don't need a graph, we just need a partition into components in the graph. To do this, you can use the fast factorization of $n$ numbers (you can read about it on the Internet, but the bottom line is that for each number in the sieve of Eratosthenes, we will not store the simplicity of this number, but any prime number not equal to it, by which our number is divided. Then factorize the number $x$ in this way: let $f_x$$-$ be any prime number by which $x$ is divisible, while $f_x < x$. Then we add the number $f_x$ to our set of easy-to-decompose $x$ and we will continue to solve the problem for $\frac{x}{f_x}$). Then we will profactorize all $n$ numbers and combine them for each divisor (I did it through the SNM, but you can just store the graph, then the asymptotics will be reduced by $log(n)$ times). Next, for each set, we calculate the multiplication of the numbers in it by the desired modulus and output these numbers. The asymptotics of the author's solution $\mathcal{O}(10^7 \cdot log(10^7) + n \cdot log(n))$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:9,option1]↵
↵
Good task: [likes:9,option2]↵
↵
Normal task: [likes:9,option3]↵
↵
Bad task: [likes:9,option4]↵
↵
Disgusting task: [likes:9,option5]↵
↵
Didn't decide: [likes:9,option6]↵
</spoiler>↵
↵
[Task I: Sergey and GCD] (https://codeforces.me/group/cBrcov20zj/contest/382218/problem/I )↵
↵
Author: [user:sdyakonov,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
We will search for the number of $r$ for each $l$ separately. <br>↵
<br>↵
Let's forget about the condition $gcd(a_l, a_r) >1$ for now. Then now the task is to find for each $l$ the minimum $r$ at which $gcd(a_l, a_{l + 1}, ...,a_r) = 1$ is executed. This can be done using bin-search, having previously written a tree of segments or sparse table to quickly find $gcd$ on a segment.<br>↵
<br>↵
We have learned to find a suffix for each $l$ on which we can choose $r$. Now we need to quickly count on this suffix the number of $r$ such that $gcd(a_l, a_r) > 1$. Note that $2\le a_i\le 1000$, so we can calculate the number of $r$ on all suffixes for all possible $a_i$.<br>↵
Let $dp[x][i]$ be the number of numbers on the suffix $a_i, a_{i + 1}, ..., a_{n - 1}$ that are not mutually prime with x. As a base of dynamics, we will make $dp[x][n] = 0$. The dynamics is recalculated simply — $dp[x][i] = dp[x][i + 1] + (gcd(x, a_i) > 1)$. By calculating such dynamics for all $x$ from $2$ to $1000$, we will be able to quickly get the number of numbers we need on the suffix.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:10,option1]↵
↵
Good task: [likes:10,option2]↵
↵
Normal task: [likes:10,option3]↵
↵
Bad task: [likes:10,option4]↵
↵
Disgusting task: [likes:10,option5]↵
↵
Not solved: [likes:10,option6]↵
</spoiler>↵
↵
[Task J: Kiril and the Journey](https://codeforces.me/group/cBrcov20zj/contest/382218/problem/J )↵
↵
Author: [user:kirill020708,2022-05-21]↵
↵
<spoiler summary="Tutorial">↵
1 solution:↵
↵
We will look for the answer from the end, assuming that upon arrival at the vertex n there will be exactly $t$ coins left. Then for $1$ step before arrival we will have $x$ coins such that $x - \frac{x}{w_1} \ge t$, and $x$ is minimal, for $2$ steps $y - \frac{y}{w_2} \ge x$, etc., where $w_1$ and $w_2$ are the weights of the roads from the optimal path. Let $d_i$ be the minimum number of coins that will be when we get from $n$ to $i$, then we can easily restore all the edge weights from $i$ in accordance with the inequality above. Now the task has been reduced to finding the shortest path from $n$ to $1$. To do this, you can use Dijkstra's algorithm (it works because the edges do not change randomly, and there are no negative edges).↵
↵
2 solution:↵
↵
We will search through the answer by bin-search: then we will make a regular Dijkstra for each possible answer (just the weights will change depending on the shortest path to the vertex). We check that the distance of the vertex $n$ is greater than or equal to $t$.↵
↵
In both solutions, the asymptotics of $\mathcal{O}(n \cdot log(n) \cdot log(10^9))$.↵
↵
The first solution is written in the code.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#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="Feedback">↵
Great challenge: [likes:11,option1]↵
↵
Good task: [likes:11,option2]↵
↵
Normal task: [likes:11,option3]↵
↵
Bad task: [likes:11,option4]↵
↵
Disgusting task: [likes:11,option5]↵
↵
Not solved: [likes:11,option6]↵
</spoiler>↵
↵
