夕立進行会報

色々と使い勝手に思いがあり、 以前作成したMarkdownパーサ を少し修正した。こちらの 実行スクリプトページ でも生成されるhtmlが変わるので注意（使ってる人はいないと思うけど）。 変更点 コードブロック &#96で囲った場合に生成されるコード部分を<code>タグで囲うように変更。またpreに付いていたクラスを削除。コード種別はcodeタグのクラスに設定。 <pre class='codeblock code_c'>//コードブロックです。ハイライトは付きません。 int a = 0; int b = a+1;</pre> ↑旧 新↓ <pre><code class='code_c'>//コードブロックです。ハイライトは付きません。 int a = 0; int b = a+1;</code></pre> インラインコード 同じく<span>から<code>へ変更。 <p>インラインコード表記は&#96;で囲み<span class='inlinecode'>int a=0;</span>ます。</p> ↑旧 新↓ <p>インラインコード表記は&#96;で囲み<code>int a=0;</code>ます。</p> 引用 以前は入れ子の引用を<span>で区別していたが、標準的な<blockquote>の入れ子に変更。 <blockquote> <span class='blockquoteNest'>&gt;は引用です。</span><br /> <span class='blockquoteNest'>ここも引用です。</span><br /> <span class='blockquoteNest'><span class='blockquoteNest'>

気づけばだいぶほったらかしになっていた。今日は競技プログラミングで出てくる「～で割ったあまりの数」についての覚え書き。 AtCoderでよく出てくる以下の文。 ～を10^9+7で割った余りを求めてください。 競プロ特有の表現なので初見は「なんのこっちゃ？」と思った。要は答えが通常の数値型では表現できない大きな数になるので、1000000007の剰余を答えろということ。 当然割る前の数を求めるとオーバーフローするので、途中途中で剰余をしながら答えを求めるわけだが。 (a + b) % m → (a % m) + (b % m) 各四則演算について上記のような置き換えが可能であることを確かめる。 証明 任意の二つの数x1,x2を以下のように定義する。 x1 = aM + c x2 = bM + d ※Mは除数、a,b,c,dは任意の整数 なお以下では除数Mでxの剰余を取ることを「x mod M」と記載する。 加算 y = x1 + x2 = (aM + c) + (bM + d) = (a + b)M + c + d y mod M = c + d = (x1 mod M)+(x2 mod M) よって (x1+x2) mod M = (x1 mod M)+(x2 mod M) 減算 加算と同じである。ただしプログラムの実装では計算過程で負の値が現れる可能性を考慮し、負値の場合Mを加算する処理を入れる。 乗算 y = x1 * x2 = (aM + c)(bM + d) = abMM + adM + bcM + cd y mod M = cd = (x1 mod M)(x2 mod M) よって (x1 * x2) mod M = (x1 mod M)(x2 mod M) 除算 ここまでは感覚的に理解してる人も多いと思う。除算だけ少し毛色が異なる。実はここが本題。 除算は以下のようにこねくり回してもMの倍数と定数項の形にできない。 y = x1 / x2 = (aM + c) / (bM + d) = aM / (bM + d) + c / (bM + d) つまるところ (x1 / x2) mod M = (x1 mod M) / (x2 mod M) は成り立たない。 ここで フェルマーの小定理 というものがある。その詳細や証明はひとまず置いてお