modint での割り算

$x \bmod B$ と $A \bmod B$ から $x / A \bmod B$ を計算するのは $A$ と $B$ が互いに素のときでないとできない。

（${}\bmod B$ で $A$ の逆元があるとは限らない）

特に $B$ が素数でも $A$ が $B$ の倍数の場合は互いに素とは限らないので注意が必要。（素数 $B$ が小さくて、割りたい数 $A$ が大きい場合には注意）

素数だから割り算できるというわけではない。ゼロ除算はできないのと同じ。

問題例

• ABC425 E - Count Sequences 2
  • もし $M$ が素数だったとしても、割りたい値が $M$ 以上だと割り算はできない
  • 問題では M が素数とは限らないので割り算を回避した解法を使うことになるが、
• ABC448 E - Simple Division
  • 解法によっては、$M$ を $P$ で割ることになる。制約では $M \leq 10^4$ で $P = 10007$ なので、$M = P$ などのケースはないが、もし M がもっと大きい制約で、$M=P$ がありえたら…….

modint で答えは分数にならないが途中で割り算が出てくる例

• 組合せ計算
• 等比数列の和
• 等差数列の和

modint での切り捨て除法

$\lfloor x/A \rfloor \bmod B$ を計算したい場合、以下の2つの解法がある。