boost の boost/integer/extended_euclidean というライブラリに1次不定方程式を拡張ユークリッド互除法で解く型があるので使ってみます． 1次不定方程式 $mx + ny = \operatorname{gcd}(m, n)$ の解 $x, y$ を1つ求めることができます． 以下のプログラムを…

boost の boost/integer/common_factor_rt というライブラリで整数配列の最大公約数や最小公倍数を求める関数があるので使ってみます． 最大公約数を求めるのは gcd_range，最小公倍数を求めるのがlcm_range です．戻り値のpairの1成分目に値が入っています…

Atcoder ABC150D D - Semi Common Multiple 時間内にはできませんでした．解説を見ながらやり直したのでまとめます． a = { a₁ ，a₂ ，... ，aN } a/2 = { a₁/2 ，a₂/2 ，... ，aN/2 } と表すことにします．a が偶数列なので，a/2 は整数列です．a の半公倍…

atcoder の D - Remainder Reminder のような，剰余 a%b を調べる問題で a と b のどちらを固定するかで議論の難しさがとても違ったので（自分は最初 a を固定して考えていて分からなくなった），この際，剰余の関数グラフをプロットして見てみる． 特別な結…

次のページの証明1：確率漸化式について自分はすこし戸惑ったので補足説明をする． AtCoder ARC 085 C - HSI (300 点) - けんちょんの競プロ精進記録 この漸化式を保証しているのは次の公式である． 確率変数 X, Y に対し，E[X] = E[E[X|Y]] である． これは…

グラフの最大流問題を解くアルゴリズムのFord-Fulkerson法のC++実装例が プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～ （蟻本）p190にあります．アルゴリズム自体は本文にある説明…

問題 L ≦ x ≦ R な自然数 x に対して， 自然数 m を法とする剰余の値 y = x%m の変域は if (R - L ≥ m) 0 ≦ y ≦ m - 1 else if ($\lfloor$L/m$\rfloor$ = $\lfloor$R/m$\rfloor$) L%m ≦ y ≦ R%m else if ($\lfloor$L/m$\rfloor$ + 1 = $\lfloor$R/m$\rfloor$…

問題 A - Diverse Word 入力された多彩な単語に対し，辞書順で次の多彩な単語を求める． 理解 多彩な単語の辞書がすぐには想像できないので書き下すことにする．「見たものは想像できる」の精神． a から始まる多彩な単語について，次の図のように木の形に単…

冪剰余 冪剰余 $a ^ b \bmod m$ を求めます．たぶん二分累乗法だと思います． #include <boost/multiprecision/integer.hpp> boost::multiprecision::powm(a, b, m) 剰余の逆元（拡張ユークリッド互除法） 剰余の逆元 $a^{-1} \bmod m$ が存在すれば求めます． （2019年10月5日追記：これはboos</boost/multiprecision/integer.hpp>…

C++ で1次元配列の最大値を求めるならばfor文を使わずに max_element を使うと楽です． 2次元配列の最大値を一度に求めるSTL関数は私は見つけられませんでしたが，各行に対して max_element を繰り返せばいいでしょう． max_element のおかげで for を書く手…

C++ でstd::queue の内容を全て削除したくなったのですが，std::queue には clear 関数がありませんでした． なので，私は直観的には queue が空になるまで pop を繰り返せばいいと思ったのですが，これはqueueのサイズに比例した時間がかかります． もっと…