けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

中国剰余定理

GCJ 2019 Round 1A B - Golf Gophers

難読。。。でも一見複雑に見えて実はシンプルという問題みたい!!! 問題へのリンク 問題概要 B の題意、結局求めたい数を V として、・x を 18 個吐いたら 18 個整数が返って来て、その和を x で割った余りを求めると、それが V % x になっている・これを …

TCO 2013 Round 2A Med TheMagicMatrix

mod. p での連立一次方程式の練習などに!!! 問題へのリンク 問題概要 × のマス目があり、そのうちの マスについては既に 以上 以下の数値が入れられている。残りの マスに 以上 以下の数値を入れる方法のうち どの行の和と、どの列の和をとっても、その一…

AtCoder ARC 012 D - Don't worry. Be Together

経路数に帰着して頑張って二項係数計算するところは面白かった! そのあとの任意 mod の二項係数処理は、今の AtCoder ではあまり出なさそうかな。 問題へのリンク 問題概要 個の座標 についての以下の値 を積算した値を で割ったあまりを求めよ。 原点から…

AtCoder ABC 103 C - Modulo Summation (300 点)

が互いに素でない場合とか一瞬だけ怖くなるけど、信じて提出する!!!!!!! 問題へのリンク 問題概要 (ABC 103 C) 個の整数 が与えられる。 様々な非負整数 に対して を で割ったあまり を で割ったあまり を で割ったあまり の総和を考えたとき、その最…

AOJ 2353 Four Arithmetic Operations

この問題の既存の解説記事は中国剰余定理によるものが多かったので、それ以外の方法を示すのはいいかもなん。 AOJ 2353 Four Arithmetic Operations 問題概要 有理数列 がある。各項は以下のように定義される: ただし は +、-、×、÷ のいずれかである。 を…

yukicoder 0187 中華風 (Hard)

Garner のアルゴリズムの verify に最適なん 問題へのリンク 問題概要 個の合同式 (mod. ) を満たす最小の正の整数 を 1,000,000,007 で割った余りを求めよ。存在しない場合には -1 をリターンせよ。 制約 < 解法 中国剰余定理で保証される最小の非負整数 を…

AOJ 2659 箸

中国剰余定理ライブラリの verify 用問題の 1 つなん AOJ 2659 箸 問題概要 箸が最初 本あった。また 個の正の整数 が与えられる。 に対して以下の 回の操作を実施したとき、最終的に の値がどのようになるかを答えよ ( が存在し得ない場合には とせよ)。 【…

TopCoder SRM 735 D1M QuadraticIdentity

ちょうど中国剰余定理シリーズやっていたので、ピンポイントだったん。 SRM 735 DIV1 Medium QuadraticIdentity 問題概要 整数 が与えられる。 (mod. ) を満たすような < ) をすべて求め、そのサイズが 500 より大きい場合には 500 以下になるまで以下の操作…

Codeforces 460 DIV2 E - Congruence Equation

中国剰余定理のことをあれこれ調べていたら勢いで解いたん 問題へのリンク 問題概要 整数 が与えられる。 mod. ) が成立するような 以上 以下の整数 を数え上げよ。 制約 は素数 < 解法 Fermat の小定理から以下のことが言える: は mod. において周期 である…