AtCoder Regular Contest 114

冷えた

Not coprime (300点)
B - Special Subsets (400点)
C - Sequence Scores (600点)
D以降

Not coprime (300点)

互いに素でないならばなにかしらの素数がgcdになれば最小になりそう．最小の $Y$ を考えるとgcdが同じ素因数を2つ以上持つ必要はないので，50以下の各素数 $p$ に対して，各 $X_i$ が $p^2$ で割りきれるなら割り切れなくなるまで $p$ で割る．割った後，全部のlcmを取って出力とする．制約が小さいので64bit整数型で答えられる．各素数で割り切れるかどうかでbitset使ってorとってもいいかも
拙解 (C++17): Submission #20931367 - AtCoder Regular Contest 114

B - Special Subsets (400点)

関数 $f(a)$ は一般に組 $(a,f(a))$ の集合として表せることを思い出すと， $a \in S$ を頂点， $(a,f(a)) \in S^2$ を有向辺として考えられる．その有効グラフはすべての頂点の出次数が1なので，有向森＋各弱連結成分につきサイクル１つ（いわゆる「なもりグラフ」）になる．そのサイクルが，条件を満たす部分集合 $T$ の最小単位になる．そのため，サイクルが $C$ 個あるとすると答えが $2^C-1$ になる．今回はサイクルの個数と弱連結成分の個数が同じなので，UnionFindで連結成分の個数 $C$ を求めて $2^C-1 \bmod 998244353$ を求めればいい．
拙解 (C++17):
Submission #20940731 - AtCoder Regular Contest 114