問題一覧 > 通常問題

No.1760 Setwise Coprime

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 : PCTprobabilityPCTprobability / テスター : NyaanNyaanNyaanNyaan tokusakuraitokusakurai
3 ProblemId : 7107 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-29 18:51:33

問題文

$1$ 以上 $N$ 以下の正整数からなる集合の組 $A,B$ であって、以下の条件を全て満たすものの個数を $998244353$ で割ったあまりを求めてください。

  • $A$ も $B$ も空でない。
  • $A$ と $B$ の共通要素は存在しない。
  • $A$ の全要素の最大公約数、$B$ の全要素の最大公約数は共に $1$ である。

制約

  • 入力は全て整数である。
  • $2 \le N \le 2 \times 10^5$

入力

$N$

出力

答えを $1$ 行に出力してください。

サンプル

サンプル1
入力
4
出力
10

例えば、$A=\{1,4\},B=\{2,3\}$ などが条件を満たします。

$A=\{\},B=\{2,3,4\}$ は $A$ が空であるため条件を満たしません。

$A=\{2,3\},B=\{3,4\}$ は $A$ と $B$ の共通要素に $3$ が存在するため条件を満たしません。

$A=\{2,4\},B=\{1\}$ は $A$ の全要素の最大公約数が $2$ であるため条件を満たしません。

サンプル2
入力
10
出力
37834

サンプル3
入力
2021
出力
199287659

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