問題一覧 > 通常問題

No.2380 Sylow P-subgroup

レベル : / AI推定難易度 : 500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 170
作問者 : 👑 箱星 / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 8807 / 自分の提出
問題文最終更新日: 2023-05-19 20:17:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 397 (群論コンテスト) (順位表) の他の問題:

Problem Statement

Find the order of a Sylow $P$-subgroup of the symmetric group of degree $N$, modulo $998244353$.

(What is the symmetric group of degree $N$?)

It is the group consisting of all bijections on the set $\{1,2,\ldots,N\}$. Its order is $N!$.

(What is a Sylow subgroup?)

Consider a group of order $m$. Let $p$ be a prime, and write $m=p^e\times k$ using a non-negative integer $e$ and a positive integer $k$ that is not a multiple of $p$. Then there exists a subgroup of order $p^e$. Such a subgroup is called a Sylow $p$-subgroup.

Constraints

  • $N$ is an integer satisfying $1\le N\le 10^{12}$
  • $P$ is a prime satisfying $2\le P\lt 998244353$

Input

$N$ $P$

Output

Output the answer modulo $998244353$.

Sample

Sample 1
Input
4 2
Output
8

The order of the symmetric group of degree $4$ is $4!=24=2^3\times 3$, so the order of a Sylow $2$-subgroup is $2^3=8$.

Sample 2
Input
1 11
Output
1

Sample 3
Input
1000000000000 998244341
Output
506700903

Output the answer modulo $998244353$.

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