競プロででてくる剰余の演算のメモ

剰余演算に関して

atcoderでたまに見かける答えに剰余を解答にする問題を見る。
競プロと剰余の記事としてはこの辺がまとまっている。
https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
大きな値はとれないので剰余にしていると思われるが、計算でよく使う分配則が本当に成り立つのかとか
これマイナスになったらどうすんの？という疑問があった

剰余はこれ
https://ja.wikipedia.org/wiki/%E5%89%B0%E4%BD%99%E6%BC%94%E7%AE%97
問題の一例はこれ
https://atcoder.jp/contests/abc178/tasks/abc178_c

剰余の分配則について

剰余の分配則はwikiの分配則参照してほしいがよく使うのは以下の式

(a+b) \bmod n = ((a\bmod n) +(b \bmod n))\bmod n

ちなみに分配則の証明は調べても出てこない。なんとなくmodの定義見てたら
いいかなという気になります。

n個の場合に成り立ちそうかどうかはここにある
https://pokuwagata.hatenablog.com/entry/2020/08/30/134727

剰余の分配則で負の値をとってしまう場合

引き算したときには分配則の左辺と右辺が異なる場合がある。 a=4,b=-3,n=2として分配則に適用すると

(a+b) \bmod n =(4-3) \bmod 2 = 1 \\
((a\bmod n) +(b \bmod n))\bmod n=((4\bmod 2) -(3 \bmod 2))\bmod 2 = (0 - 1)\bmod2 = -1  

となる（上段が分配則の左辺、下段が右辺）。
bがそもそも負の数をとってはいかんのだがそれはさておき競プロでは剰余にした結果
そういう計算が生じることもある。今回の問題なんかはそれである。
さて、どう対策するかというと解答を見てみるとどうやら

(a-b) \bmod n = ((a - b)\bmod n + n) \bmod n 

が成り立ちそうな気配である。

\begin{align}
((a - b)\bmod n + n) \bmod n &= ((a-b) \bmod n + n \bmod n) \bmod n\\
&=((a-b) \bmod n) \bmod n \\
&=(a-b) \bmod n
\end{align}

確かに成り立ちそう。
求めたいのは最終行だがそのまま分配則で計算すると上の例の通りマイナスになってしまうため
nを足してあげているということだ。誰が考え付いたのかわからんが有り難く使わせてもらう。

オーバーフローする値の剰余を求めるとき

簡単に言うとpythonのpowなんかでは問題がでないが素直にコーティングするとオーバーフローするやつである
https://qiita.com/R_olldIce/items/ab3f382643e92122f8ef
↑はpythonのpowの話

例えば10^45の剰余をとろうとする

fn main() {
let x: i32 = 10; // or any other integer type
println!("{}",x.pow(45 as u32) % 3);
}

これはもうエラーである（thread 'main' panicked at 'attempt to multiply with overflow'～）
ここで出てくるのが二分累乗法という方法です。
原理はここ参照
https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#4-%E7%B4%AF%E4%B9%97-an

rustでは以下のようになります（binary_poweringで実装）
https://zenn.dev/yuucu/scraps/df5c890cd38777
からもらってきました

fn main() {
let x: i64 = 10; // or any other integer type
println!("{}",binary_powering(x,45,3) );
}

pub fn binary_powering(mut a: i64, mut n: i64, m: i64) -> i64 {
    let mut res = 1i64;
    let m = if m != 0 { Some(m) } else { None };
    while n > 0 {
        if n & 1 != 0 {
            res *= a;
            if let Some(m) = m {
                res %= m
            }
        }
        a *= a;
        if let Some(m) = m {
            a %= m;
        }
        n >>= 1;
    }
    res
}