競技プログラミングでは を用いた数え上げ問題が頻出します。このとき途中で割り算を用いますが、計算途中のオーバフローを避けるためモジュラ逆数というものを使いますが、このモジュラ逆数はFermat*1の小定理やEuler*2の定理といったものを利用して計算さ…

Carmichael*1函数はCarmichaelの定理に出てくる函数ですが、逆にこれ以外では出てこないと思います。しかし、定義が少し煩雑であるのと、この函数が返す値がEuler*2のトーシェント函数の与える値の約数になっていることについての証明をしたいので1つの記事…

Euler*1のトーシェント函数*2とは主に と表記される、整数論における函数です。次のように定義されます。 $$ \varphi(n) = \#\{k \mid 1 \leq k \leq n,\ \gcd(n,\,k) = 1\} $$ 日本語で書くと から までの整数のうち、 と互いに素な整数の個数となります。 …

ABC193のE問題は連立合同式についての問題でした。これは中国式剰余定理によって解を求めるものです。他にも拡張Eulerの定理についての証明においても中国式剰余定理は登場します。 名前と背景 定理の主張 証明(互いに素、二元のとき) 解の存在 解の一意性 …

ARC113のB問題は としたとき の列が4(の約数)の周期で循環すること、 の列が2(の約数)の周期で循環することを利用する問題でした。これらについては実際に実験して求めた人やFermatの小定理やEulerの定理によって説明しようとした人などがいました。しかしこ…

アフィン変換についての記事を書いたのですが一次変換(線型変換)についての部分が長くなったので分割してこちらに書くとことにします。 基底と行列 一次変換の合成 一次変換の例(2次元) 恒等操作(単位行列) 原点を中心とする相似変換と零行列 原点を中心とす…

ABC189のE問題はアフィン変換を合成していく問題でした。今回はこのアフィン変換についてまとめていきたいと思います。 平行移動 行列とベクトルの組によるアフィン変換の表現 平行移動を先にすると アフィン変換の合成 アフィン変換の行列表現 ABC189-E $ \…