問題一覧 > 通常問題

No.2081 Make a Test Case of GCD Subset

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 39
作問者 : taiga0629kyoprotaiga0629kyopro / テスター : hari64boli64hari64boli64 👑 ygussanyygussany
4 ProblemId : 8496 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-17 20:44:26

問題文

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$

  • $0 \le M < 998244353$
  • 入力は全て整数
  • 出力

    以下のように $1$ 行目に数列の長さ $N$ を、$2$ 行目に数列 $A$ を出力してください。 答えが複数存在する場合、どれを出力しても正解とみなされます。

    $N$
    $A_1$ $A_2$ $\dots$ $A_N$

    また出力は以下の制約を満たす必要があります。

    出力の制約

  • $1 \le N \le 10^5$
  • $1 \le A_i \le 10^5$
  • $A$ の要素は全て異なる
  • 出力は全て整数
  • サンプル

    サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。