はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるmod計算問題まとめ

階乗の逆元をかけて計算したり、組合せ数学関連

フェルマーの小定理と繰り返し二乗法をつかって逆元を求める技を利用 解説 uwiさんのここに組合せの全てがある
問題

【発展的話題】 CRT(中国人剰余定理)とルーカスの定理を使うと解ける二項定理

前提知識のCRT

上記の2問題で求められる計算は
C(a,b) mod m
a,b <= 10^18, m<10^6(素数じゃないかも)
である。
 
計算手順
1. modを素因数分解する
2. 各素因数の累乗をmodとして二項定理を解く([https://www37.atwiki.jp/uwicoder/pages/2118.html#id_6779f709:title=uwiさんのサイトのこの部分の手法を使う])
3. それぞれ解けた答えでCRTを解くと答えが出る

問題

平方剰余

問題

ウィルソンの定理

(M-1)! ≡ -1 (mod M)という定理がウィルソンの定理 解説
問題