AtCoder Regular Contest 114のきろく - Flkanjin’s 競プロ録

2問しか解けなかった...

A - Not coprime (300点)
B - Special Subsets (400点)
C - Sequence Scores (600点): 未提出
D - Moving Pieces on Line (600点): 未提出
E - Paper Cutting 2 (700点): 未提出
F - Permutation Division (900点): 未提出
結果、感想

A - Not coprime (300点)

互いに素であるかどうかが争点なので、素数の積で考えればいいです。 $50$ 以下の素数は $15$ 個であり、bit全探索して答えを求めます。なお、 $50$ 以下の全素数の積は $614\,889\,782\,588\,491\,410$ であり、long long型に収まります。

全ての $i$ $(1 \leq i \leq N)$ について $i \rightarrow f(i)$ の有向辺から成るグラフを考えます。このグラフでは全ての頂点の出次数は $1$ であり、全ての連結成分について辺を辿っていくとループに辿り着きます(自己辺もループとみなします)。さて、 $a \in T \Longrightarrow f(a) \in T$ であることよりある頂点を選んでそこから辺を辿っていける全ての頂点が $T$ に属すことになります。しかし $a,\,b \in T$ $a \neq b$ のとき $f(a) \neq f(b)$ であることからループ部分しか $T$ に属しません。よって各ループが $T$ に属すかどうかで連結成分数を $n$ として候補は $2^n$ 個となりますが、 $T$ は空ではいけないため $2^n - 1$ が答えとなります。