No.2081 Make a Test Case of GCD Subset
タグ : / 解いたユーザー数 42
作問者 :
taiga0629kyopro
/ テスター :
ygussany
hari64
問題文
taiga 君は次のような問題を作りました。
GCD Subset
長さ $N$ の正整数列 $A$ が与えられます。 ここで、$A$ の要素はすべて互いに異なります。 $\lbrace 1,2, \dots ,N \rbrace$ の空でない部分集合 $S=\lbrace S_1,S_2,\dots,S_k \rbrace$ のうち次の条件を満たすものを良い集合と呼ぶことにします。
- $\gcd(A_{S_1},A_{S_2},\dots,A_{S_k}) \ge 2$ （ただし、$\gcd(X_1,X_2,\dots,X_k)$ で $X_1,X_2,\dots,X_k$ の最大公約数を表す。）
$\lbrace 1,2, \dots ,N \rbrace$ の空でない部分集合は $2^N-1$ 個ありますが、そのうち良い集合の個数を $998244353$ で割った余りを求めてください。
整数 $M$ が与えられます。問題 "GCD Subset" の答えが $M$ となるような数列 $A$ を $1$ つ出力してください。
入力
$M$
出力
以下のように $1$ 行目に数列の長さ $N$ を、$2$ 行目に数列 $A$ を出力してください。 答えが複数存在する場合、どれを出力しても正解とみなされます。
$N$ $A_1$ $A_2$ $\dots$ $A_N$
また出力は以下の制約を満たす必要があります。
出力の制約
サンプル
サンプル1
入力
3
出力
3 1 3 6
$N=3$, $A=(1,3,6)$ とすれば良い集合となるのは $\lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 2,3 \rbrace$ の $3$ 個となり条件を満たします。 他にも例えば、良い集合の個数が $998244353+3$ 個となるようなものを出力しても正解になります。
また、以下のように出力すると不正解となるので気をつけてください。
3 1 3 6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。