問題概要
正整数 $n, m, k$ ($n \neq m $) が与えられる．正整数であって，$n, m $ のどちらか一方でのみ割り切れる数の内，小さい方から $k$ 番目のものを求めよ．
制約
- $1 \leq n, m \leq 10^8$
- $1 \leq k \leq 10^{ 10 }$
- $n \neq m $
AtCoder Beginner Contest 341, E : Alternating String
問題概要
$0$ と $1$ からなる $n$ 要素の列 $S = S_1, S_2, \dots S_n$ ($S_i \in { 0, 1 }$) が与えられる．クエリが $q$ 個与えられるので，順に処理せよ．クエリは以下の 2 種類からなる：
- $( 1, l, r )$ : $l \leq i \leq r$ なる $i$ について，$$S_i \leftarrow 1 - S_i$$ と更新する*1．
- $( 2, l, r )$ : $l \leq i < r$ なる任意の $i$ について $$S_i \neq S_{ i + 1 }$$ かどうか判定する．
制約
- $1 \leq n, q \leq 5 \times 10^5$
*1:$0$ と $1$ を反転する．
AtCoder Beginner Contest 341, F : Breakdown
問題概要
$n$ 頂点 $m $ 辺からなるグラフ $G = ( V, E )$ がある．ここで，$\forall u, ( u, u ) \not \in E$ かつ $( u, v ) \in E \Leftrightarrow ( v, u ) \in E$ である（i.e., $G$ は単純無向グラフである）．頂点 $u \in V$ には正整数 $W_u$ が紐付けられており，また，$A_u$ 個の駒が置かれている．
$G$ の頂点 $u \in V$ に対し，open neighbor $N( u )$ を
\begin{equation*}
N( u ) = \{ v \mid ( u, v ) \in E \}
\end{equation*}
で定義する*1．
駒が置かれている頂点が存在する限り，次の操作を繰り返す：
- $1$ つ以上の駒が置かれている頂点を選び，それを $x$ とする．
- $x$ から駒を $1$ つ取り除く．
- $N( x )$ の部分集合 $S \subseteq N( x )$ であって，$$\sum\limits_{ u \in S } W_u < W_x$$ なものを選ぶ．
- $S$ に含まれる頂点それぞれについて，新たな駒を $1$ つ置く．
最大で何回の操作を行えるか？ なお，無限回の操作を行うことはできない．
制約
- $2 \leq n \leq 5 \times 10^3$
- $1 \leq m \leq \min\left( \frac { n ( n - 1 ) } 2, 5 \times 10^3 \right)$
- $1 \leq W_u \leq 5 \times 10^3$
- $0 \leq A_u \leq 10^9$
*1:要するに隣接している頂点の集合．
AtCoder Beginner Contest 340, F : S = 1
問題概要
整数 $x, y$ ($x \neq 0$ or $y \neq 0$) が与えられる．
以下の条件を満たす整数 $a, b$ を出力せよ．
- $-10^{ 18 } \leq a, b \leq 10^{ 18 }$
- 二次元平面 $\mathbb R^2$ 上の点 $( 0, 0 ), ( x, y ), ( a, b )$ を頂点とする三角形の面積が $1$ に等しい
制約
- $-10^{ 17 } \leq x, y \leq 10^{ 17 }$
- $( x, y ) \neq ( 0, 0 )$
AtCoder Beginner Contest 340, E : Mancala 2
問題概要
$0$ から $n - 1$ で番号付けられた $n$ 個の箱があり，最初，箱 $i$ には $A_i$ 個のボールが入っている．
$i = 1, 2, \dots, m $ に対し順に以下の手続きを実行する．
- 変数 $c$ を用意し，$c \leftarrow 0$ とする．
- 箱 $B_i$ の中のボールを全て取り出し，手に持つ．
- 手にボールをひとつ以上持っている間，次の処理を繰り返す．
- $c \leftarrow c + 1$ とする．
- 手に持っているボールをひとつ，箱 $( B_i + c ) \bmod n$ に入れる．
操作完了後に各箱に入っているボールの個数を求めよ．
制約
- $1 \leq n, m \leq 2 \times 10^5$
- $0 \leq A_i \leq 10^9$
- $0 \leq B_i < n$
