一次合同方程式 を解くことを考えます。競技プログラミングでは稀に必要となる知識で、たとえば以下のような問題で要求されます。 atcoder.jp この記事では、 【理論編】一次合同方程式 の解の個数 【実装編】拡張ユークリッド互除法による一次合同方程式の…

昨日のABC F問題のように、既約分数（有理数）を「(mod 素数) における逆元を用いて整数として表現する」ことが問われる場合があります。 atcoder.jp この記事では 分数をなぜ整数として表現できるのか どうやってその値を算出するのか という辺りを丁寧にま…

2次元座標系における点 と点 間のマンハッタン距離 は、 と定義されます。簡単に言うと「斜め移動はできず、縦横方向にしか動けない場合の距離」です。 マンハッタン距離上図では、中央の緑マスからのマンハッタン距離を各マスに記しています。また、中央か…

「エラトステネスの篩」は素数列挙に使われる効率的なアルゴリズムです。 「2」から「対象とする最大値」までを「素数候補」とする 残っている数のうち最小値を「素数」と判定して「素数候補」から除外する 2. で素数と判定した倍数を、全て「素数候補」から…

私の世代は授業として整数を扱わなかったので、ユークリッドの互除法についても「名前はよく聞く」くらいで実態は毎回調べていました。 そんなことを人生で10回くらい繰り返している気がするので、そろそろ証明をちゃんと理解してメソッドを覚えたいと思いま…

今日こちらの問題を解いていて、途中で調和級数的なものが出てきました。atcoder.jp この問題自体は残念ながら までしか落とせなくて自力では解けなかったのですが、 へ落とす発想として色々弄っていると調和級数的なものが出てきたのでした。調和級数とは以…

計算量で対数時間 というものをよく見かけると思いますが、これが具体的にどの程度のものか、感覚で理解してみます。 まず大前提として、 の底は（計算機科学においては一般に）2 です。何故 2 なのかというと、分割統治法の考え方で問題サイズを半分にする…

いい頭の体操になる問題です。 問題 を素数とする。 が全て素数となるような を全て求めよ。 考え方 まず、差に関する条件から となります。 この条件で少し考えてみると、 という組が思い付きます。素数の組で、差はそれぞれ で全て素数です。これ以外に条…

タイトルの問題ですが、パッと見「は無理数か？」という教科書問題が思い浮かびます。教科書問題では、（は互いに素な非零整数）と仮定して背理法で無理数であることを示します（ともに偶数であることを示せます）。 これと同じように、を有理数と仮定してみ…

久々に「純粋なブログ」というものを始めてみました。 最近は無為に時間を過ごすことも多く、仕事でもプログラムを書くことが中心なので、言語野が劣化してきた感覚があります。その対策や、日々何か成長していきたいという思いから「ただのブログ」を立ち上…