投稿者 NOSS | 2019-10-22
こんにちは、NOSSです。
今回はmod演算についての講習会を行いました。
また、3名の留学生の方に見学に来ていただきました。
講習会
秋学期に入って1回目の講習会ですが、かなり数学よりの内容になってしまいました。
- ユークリッド互除法、拡張ユークリッド互除法
- 繰り返し2乗法
- modの逆元
- フェルマーの小定理
基本的なmod演算はすでに経験がある人も多いかと思いますが、modの逆元が存在するのはかなり以外だったと思います。
参考サイト
- 拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜
- 「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜
- モジュラ逆数 - Wikipedia
コンテスト
あまりを取る問題を中心に集めました。
簡単な解説
けんしょう先生のお菓子配り
$a % b = 0$ ならば $0$、そうでないならば $b - (a % b)$ が答え。
□□□□□
$a \times b$ の長方形 $(a < b)$ を作り、あまりが $c$だとすると、$a \times b + c = N$ となる。
ここで $a$ を決めると $b = \lfloor N/a \rfloor, c = N % a$ と求められる。
よって $1 \le a \le \sqrt{N}$ の各 $a$ について $b,c$ を求め、$\min(b-a+c)$ をとれば答えが求められる。
Training Camp
$N! \mod 10^9+7$ を求める。
for文で$1,2,…,N$をかけていけばよい。
ただし、64bit整数を使うこととかけ算を行う毎にmodをとる必要があることに注意。
Modulo Summation
$f(m)$ は $m = (a_1 a_2 a_3 … a_N) - 1$ のとき最大値 $\sum_{i=1}^{N} (a_i - 1)$ をとる。
Factors of Factorial
まず約数の個数の求め方を考える。$A = p_1^{k_1} p_2^{k_2} … p_m^{k_m}$ と素因数分解できるとき、その約数の個数は $(k_1 + 1)(k_2 + 1)…(k_m + 1)$ で求められる。
よって $N!$ の素因数分解ができれば答えが求められる。 これは $1 \le i \le N$ の各 $i$ を素因数分解した結果から求めることができる。
多重ループ
重複組み合わせ。$\binom {N+K-1}{K} = \frac{(N+K-1)!}{(N-1)!K!}$