中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに NTT データ数理システムでアルゴリズムの探求をしている大槻 (通称、けんちょん) です。最近のマイブームなアルゴリズムは NTT (Number-Theoretic Transform) です。 NTT は FFT (高速フーリエ変換) の亜種です。日本語では高速剰余変換と呼ばれることが多いです。FFT ではどうしても登場しがちな「計算途中での丸め誤差」を回避するテクニックとして有効です。NTT を実運用する際には以下のような楽しい初等整数論的トピックたちを使用することになってすごく面白いです。 ${\rm mod}. p$
再帰関数を学ぶと、どんな世界が広がるか - Qiita
0. はじめに 再帰関数は初めて学ぶときに壁になりがちで なんとなくわかった...けれど どんな場面で使えるのだろう...いい感じの例を探したい！ という気持ちになりがちです。再帰関数は、なかなかその動きを直感的に想像することが難しいため、掴み所が無いと感じてしまいそうです。 そこで本記事では 再帰関数の動きを追いまくることで、再帰関数自体に慣れる 再帰的なアルゴリズムの実例に多数触れることで、世界を大きく広げる！ ことを目標とします。特に「再帰関数がどういうものかはわかったけど、使いどころがわからない」という方のモヤモヤ感を少しでも晴らすことができたら嬉しいです。なお本記事では、ソースコード例に用いるプログラミング言語として C++ を用いておりますが、基本的にはプログラミング言語に依存しない部分についての解説を行っています。 追記 1. 再帰関数とは 再帰の意味はとても広いです。自分自
拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜 - Qiita
NTT データ数理システムでアルゴリズムの探求をしている大槻 (通称、けんちょん) です。好きなアルゴリズムは二部マッチングです。今回は、歴史の記録に残る最古のアルゴリズムの 1 つとして知られるユークリッドの互除法について書きます。 ユークリッドの互除法は、最大公約数を求めたり、一次不定方程式 $ax + by = c$ に応用したりなど、大学受験でもお馴染みのアルゴリズムですが、整数論的アルゴリズムや数え上げアルゴリズムにおいて根幹を成す重要なものでもあります。 今回の記事では特に、一次不定方程式 $ax + by = c$ の整数解を一般に求めるアルゴリズムとして知られる「拡張ユークリッドの互除法」の理解を目指します。 1. ユークリッドの互除法とは ユークリッドの互除法は、2 つの整数 $a$, $b$ の最大公約数を効率よく求めるアルゴリズムです。本記事では $a$ と $b$
AtCoder 版！蟻本 (中級編) - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0 はじめに 前回の初級編に続いて、今度は中級編です。 プログラミングコンテストチャレンジブック (通称、蟻本) は日本の競技プログラミングの普及に多大な貢献を果たしています。多くの競技プログラマたちが蟻本を手に取りながらコンテストの世界に没入して行きます。しかしながら発売から 6 年以上経過する間に競技プログラミング界隈には大きな変化がありました。蟻本的に影響が大きいのは以下の点です: POJ が国内ではあまり使用されなくなった (計算速度が遅いなど) AtCoder 上で問題を解くことが盛んになった 今回はこの完全解決を試みます。具
AtCoder 版！蟻本 (初級編) - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0 はじめに プログラミングコンテストチャレンジブック (通称、蟻本) は日本の競技プログラミングの普及に多大な貢献を果たしています。多くの競技プログラマたちが蟻本を手に取りながらコンテストの世界に没入して行きます。しかしながら発売から 6 年以上経過する間に競技プログラミング界隈には大きな変化がありました。蟻本的に影響が大きいのは以下の点です: POJ が国内ではあまり使用されなくなった (計算速度が遅いなど) AtCoder 上で問題を解くことが盛んになった 今回はこの完全解決を試みます。具体的には、蟻本に載っている例題たち (ほと
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
