問題一覧 > 通常問題

No.2380 Sylow P-subgroup

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 166
作問者 : 箱星 / テスター : 👑 p-adic
0 ProblemId : 8807 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-19 20:17:44

問題文

NN 次対称群のシロー PP 部分群の位数を 998244353998244353 で割った余りを求めてください。

(NN 次対称群とは)

集合 {1,2,…,N}\{1,2,\ldots,N\} 上の全単射全体からなる群です。位数は N!N! です。

(シロー部分群とは)

位数 mm の群を考えます。pp を素数とし、負でない整数 ee と pp の倍数でない正の整数 kk を用いて m=pe×km=p^e\times k と表します。このとき位数が pep^e の部分群が存在します。これをシロー pp 部分群といいます。

制約

  • NN は 1≤N≤10121\le N\le 10^{12} をみたす整数
  • PP は 2≤P<9982443532\le P\lt 998244353 をみたす素数

入力

NN PP

出力

答えを 998244353998244353 で割った余りを出力してください。

サンプル

サンプル1
入力
4 2
出力
8

44 次対称群の位数は 4!=24=23×34!=24=2^3\times 3 なので、シロー 22 部分群の位数は 23=82^3=8 です。

サンプル2
入力
1 11
出力
1

サンプル3
入力
1000000000000 998244341
出力
506700903

998244353998244353 で割った余りを出力してください。

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