この記事は「Infocom Advent Calendar 2023」カレンダーの18日目の記事です
今年も競プロのネタです。
「何らかの数式の計算結果を求める問題で数式の解の桁が大きくなるので、intで収まる程度の数字で割った余りを答えよ。」
といったタイプの問題が良く出ます。
今まで、計算の仕方もわからないし、余りを出力する意味もわからなかったのですが、今年読んだ対策本に数学の性質を利用して解くと解説があり、より深く習得するために本記事に記します。ただ、
余りを出力することが、現実的に何かに役立つのかは未だよくわかっていません。
『競技プログラミングの鉄則] 米田 優峻 (著)を参考にして記載しています。
一つ目の性質
足し算、引き算、掛け算の場合、好きなタイミングで余りをとっても答えは変わらない。
ただし、計算結果が負の数になる場合は、割る数を足す工夫が必要です。
数式で書くと以下。
//m, nをxで割った商(a, c)と余り(b, d)
m = ax + b
n = cx + d
(m + n)%x = (m%x + n%x)%x = (b + d)%x
(m - n)%x + ((m < n) ? x : 0)= (m%x - n%x)%x =(b - d) < 0 (b-d+x)%x: (b-d)%x (m > n)
(m * n)%x = (m%x * n%x)%x =(b * d)%x
足し算と引き算はこの数式を見ればなんとなくわかります。
(m < n)の場合、(m - n)%xが負の数となるため、+xする必要があります。
掛け算については、mをn回足した余りは、足し算の性質を利用して、(b*n)%x。同じようにnをb回足すと考えると、(b * d)%xが導けます。
二つ目の性質
割り算の場合でxが素数かつnがxの倍数でない場合、以下に置き換えても計算結果は変わらない。
(m / n)%x = m%x / n%x = (m%x * (n%x)^(x-2))%x
これは、フェルマーの小定理というのが関連してるそうでわかりそうにないので丸暗記します。
切り出すと、 /n%x は、*n^(x-2)の%x。
x-2乗で数字が大きくなる対策として、一つ目の性質を利用して、掛ける度に余りを取ります。更に計算量を減らすには繰り返し２乗法を使うそうです。
a^4%x = a^2%x * a^2%x
a^8%x = a^4%x * a^4%x
xが素数かつnがxの倍数でない場合と条件が限定されているので使いどころは注意が必要そうです。
#検証用のクラス
public class Amari {
public int plusAmari(int m, int n, int x) {
return (m % x + n % x) % x;
}
public int minusAmari(int m, int n, int x) {
int o = (m % x - n % x);
o = (o < 0) ? o + x : o;
return o % x;
}
public int multifyAmari(int m, int n, int x) {
return (m % x * n % x) % x;
}
public int devideAmari(int m, int n, int x) {
/*
* (m/n)%x
* (→ (m%x / n%x)%xは成り立たない )
* = (m%x * (n%x)^(x-2))%x
*/
return (int) ((m % x * Math.pow(n % x, x - 2)) % x);
}
//(n%x)^(x-2) が大きい数字となる対策として都度、余りを取る
public int devideAmariBig(int m, int n, int x) {
//Math.pow(n%x, x - 2)%xの計算
int nx = n % x;
int nn = nx;
for (int i = 0; i < x - 2 - 1; i++) {
nn = multifyAmari(nn, nx, x);
}
return (int) ((m % x * nn) % x);
}
}
応用
これらを使えば、pCr = p!/(r!*(p-r)!)をxで割った余りを求める問題が計算可能になります。
①p!%xを計算。mとする。
②r!%x、(p-r)!%xを計算。nとする。
③(m/n)%xを二つ目の性質を使って計算（mとnはあまりを取ったあとの数字のため、m/nを計算してはいけない）
AtCoderの過去問といて習得しようと思います。