問題一覧 > 通常問題

No.2081 Make a Test Case of GCD Subset

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

問題文

taiga 君は次のような問題を作りました。

GCD Subset

長さ NN の正整数列 AA が与えられます。 ここで、AA の要素はすべて互いに異なります。 {1,2,,N}\lbrace 1,2, \dots ,N \rbrace空でない部分集合 S={S1,S2,,Sk}S=\lbrace S_1,S_2,\dots,S_k \rbrace のうち次の条件を満たすものを良い集合と呼ぶことにします。

  • gcd(AS1,AS2,,ASk)2\gcd(A_{S_1},A_{S_2},\dots,A_{S_k}) \ge 2 (ただし、gcd(X1,X2,,Xk)\gcd(X_1,X_2,\dots,X_k)X1,X2,,XkX_1,X_2,\dots,X_k の最大公約数を表す。)

{1,2,,N}\lbrace 1,2, \dots ,N \rbrace の空でない部分集合は 2N12^N-1 個ありますが、そのうち良い集合の個数を 998244353998244353 で割った余りを求めてください。

整数 MM が与えられます。問題 "GCD Subset" の答えが MM となるような数列 AA11 つ出力してください。

入力

MM

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

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

    NN
    A1A_1 A2A_2 \dots ANA_N

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

    出力の制約

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

    サンプル1
    入力
    3
    出力
    3
    1 3 6

    N=3N=3, A=(1,3,6)A=(1,3,6) とすれば良い集合となるのは {2},{3},{2,3}\lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 2,3 \rbrace33 個となり条件を満たします。 他にも例えば、良い集合の個数が 998244353+3998244353+3 個となるようなものを出力しても正解になります。

    また、以下のように出力すると不正解となるので気をつけてください。

    3
    1
    3
    6

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。