library-checker-problems icon indicating copy to clipboard operation
library-checker-problems copied to clipboard

Published 20 hours ago • verified publisher icon yosupo06

[問題案] n! mod p

Open yosupo06 opened this issue 5 years ago • 5 comments

問題ID: 募集 問題名: 募集

問題概要

n, pが与えられる。n! % pを求めてください

入力

N P

制約

  • 1 <= N <= P <= 10^9

議論

  • Pは素数？
  • 任意mod?
  • 制約は？

yosupo06 avatar Oct 06 '19 18:10 yosupo06

@koba-e964 さんがやっていただけるそう ありがたい(もしかしてコメントないとassign出来ない？)

yosupo06 avatar Oct 15 '19 11:10 yosupo06

私にアサインしてください。

koba-e964 avatar Oct 15 '19 12:10 koba-e964

これ、忘れ去られていたらやりますが…。

Maruoka842 avatar May 13 '20 10:05 Maruoka842

@koba-e964

yosupo06 avatar May 13 '20 12:05 yosupo06

代わりにやっていただけると助かります 🙏

koba-e964 avatar May 15 '20 02:05 koba-e964

これ作業に入った形跡はあるけど、制約は決まっていないですね。 合成数だと、素べきごとに解いてCRTということだと思うんですが、CRTとかは別の問題で面倒を見ることにして、素数でよいでしょうか。

素数ならば、アルゴリズムは変わらないので 998244353 固定でよいと思います。 この場合、埋め込みを使った階乗計算という別解があるので、verify できるライブラリが増えます。

maspypy avatar Apr 03 '23 11:04 maspypy

mod 998244353 で、作業者募集でお願いします。

maspypy avatar Apr 19 '23 07:04 maspypy

作業します。

maspypy avatar Nov 02 '23 17:11 maspypy

done https://github.com/yosupo06/library-checker-problems/pull/1051

maspypy avatar Nov 09 '23 16:11 maspypy