公式など

• あまり

  • $a$ を $b$ で割ったときの余りを $r$ としたとき、$0 \leq r < b$ なことに注意
    • 例
      • Q5. A を割ると B あまる数 | アルゴ式
      • ARC 176 B - Simple Math 4
  • 余りの冪等性
    • $(x \bmod a) \bmod a = x \bmod a$
  • 余りの順序
    • $a < b$ のとき、$(x \bmod a) \bmod b = x \bmod a$
      • 例えば mod 5 をした後に mod 12 をしても変わらない
    • 応用例
      • エクサウィザーズ2019 D - Modulo Operations (解説は 挿入DP を参照)

• 整序関係

  • ax | bx ⟺ a | b (x ≠ 0 のとき)

• 合同式

  • $ab \equiv ac \pmod{an}$ ならば $b \equiv c \pmod n$
    • $a\neq 0$ のとき
    • 逆も成り立つ
  • $b \equiv c \pmod{an}$ ならば $\lfloor b/a \rfloor \equiv \lfloor c/a \rfloor \pmod{n}$
    • $a \neq 0$ のとき
    • 参考: ARC167 B, ARC167 の A問題, B問題を画像でまとめてみました - ぱるまの日記

• 高度合成数

  • 高度合成数の一覧 | アルゴ式

• gcd と lcm はかけ算に関して分配的

  • $a \gcd(b, c) = \gcd(ab, ac)$
  • $a \operatorname{lcm}(b, c) = \operatorname{lcm}(ab, ac)$
  • 特に $(\mathbb{N}, \gcd, \times)$ は半環を成す
    • min, plus 代数と同様。素因数分解したときの指数で min plus したものだと思えば良い。

• ルジャンドルの公式

  • $N!$ の素因数分解における $p$ の指数を $e_p(N)$ と書く。
    • $N!$ の $p$-進付値と呼ばれるもの
  • $\displaystyle e_p(N) = \sum_{k=1}^\infty \left\lfloor \frac{N}{p^k}\right\rfloor$ が成り立つ
  • double counting をすると得られる。

拡張ユークリッドの互除法

理論面

• $a$ と $b$ が互いに素とする

  整数変数 $x, y$ に関する方程式 $ax + by = 1$ は解を持つ。

  とくに $|x| \leq |b|$、$|y| \leq |a|$ をみたす解が存在する。

  拡張ユークリッドの互除法をすると、自然に$|x| \leq |b|$、$|y| \leq |a|$ をみたす解が得られる。

• $ax + by = 1$ が解を持つ（$a$ と $b$ が互いに素）ならば、$ax + by = d$ も解を持つ。

  • $ax + by = 1$ の解として $(x_0, y_0)$ があるとき、$(dx_0, dy_0)$ は $ax + by = d$ の解になる。

• $d$ が $\gcd(a,b)$ の倍数のとき $ax + by = d$ は解を持ち、そうでないとき解を持たない。

  • 例えば、$4x + 6y = 3$ は解を持たない（左辺は偶数、右辺は奇数なので当然）

• 参考

  • ベズー係数とN項の拡張ユークリッドの互除法 | 東京科学大学デジタル創作同好会traP

実装面

• 拡張ユークリッドの互除法のライブラリ
  • Rust の場合 num_integer クレートにある
    • https://docs.rs/num-integer/latest/num_integer/trait.Integer.html#method.extended_gcd
  • Python の場合 sympy にある。

問題例

• ABC340 F - S = 1