アルゴリズム論特論(塩田)第13回 (5) 今日のまとめ

前へ / 戻る $\newcommand{\ol}[1]{\overline{#1}}$ $\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$ $\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$ $\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$

参考

  • 中国剰余アルゴリズムデモプログラム CRA.py

今日のまとめ

  • 互いに素な法 $m_1$, $\cdots$ $m_k$ については、「 $\bmod\ m_1\times\cdots\times m_k$ の情報」は 「 $\bmod\ m_i$ の情報の組」に読み替えられる。
  • その読み替えの計算量は $\log^2$ オーダーである。

自宅学習の例

  • デモプログラムでビット数・式の個数を変えて計算量を体感する。
  • 違う数字で数当てゲームを作ってみる。
  • html の ソースを読んで、Javascript の BigInt の使い方を覚える。