逆元
この問題の既存の解説記事は中国剰余定理によるものが多かったので、それ以外の方法を示すのはいいかもなん。 AOJ 2353 Four Arithmetic Operations 問題概要 有理数列 がある。各項は以下のように定義される: ただし は ＋、－、×、÷ のいずれかである。 を…
ちょうど中国剰余定理シリーズやっていたので、ピンポイントだったん。 SRM 735 DIV1 Medium QuadraticIdentity 問題概要 整数 が与えられる。 (mod. ) を満たすような < ) をすべて求め、そのサイズが 500 より大きい場合には 500 以下になるまで以下の操作…
中国剰余定理のことをあれこれ調べていたら勢いで解いたん 問題へのリンク 問題概要 整数 が与えられる。 mod. ) が成立するような 以上 以下の整数 を数え上げよ。 制約 は素数 < 解法 Fermat の小定理から以下のことが言える: は mod. において周期 である…
解けたけどもっとちゃんと整理しないとなん 問題へのリンク 問題概要 N 個の整数 a_1, a_2, ..., a_N が与えられる (0 <= a_i <= 9)。これを並び替えて順につないでできる整数 (leading zero は除く) として考えられるものの総和を 109 + 7 で割った余りで求…
1. 典型的な二項係数の求め方 (1 ≦ k ≦ n ≦ 107 程度) 競プロをしていると、nCk mod. p を計算する場面にしばしば出くわします。時と場合によって色んな方法が考えられますが、以下のものを頻繁に使用するイメージです。多くの AtCoder のトッププレイヤーた…
