2013-09-16 MOD乗算 MODをとる場合でも大きい数字の掛け算はオーバーフローしてしまうので、工夫をしなければならない。 片方の数字をの足し算で表す。 ここで、は2進数表記でのnビット目を示す。ただし、0ビットから始まるとする。 aを括弧内に入れる。 は1か0しか値を取らないので、ビットが立っている部分の和が答えになる。 を例にとる。