活動日誌'19 No.015

投稿者 NOSS | 2019-10-22

こんにちは、NOSSです。
今回はmod演算についての講習会を行いました。

また、3名の留学生の方に見学に来ていただきました。

講習会

秋学期に入って1回目の講習会ですが、かなり数学よりの内容になってしまいました。

ユークリッド互除法、拡張ユークリッド互除法
繰り返し2乗法
modの逆元
フェルマーの小定理

基本的なmod演算はすでに経験がある人も多いかと思いますが、modの逆元が存在するのはかなり以外だったと思います。

参考サイト

コンテスト

YNU CPC 2019 VC 026 A

あまりを取る問題を中心に集めました。

簡単な解説

けんしょう先生のお菓子配り

$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!}$

講習会