drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder 旧ARC-D 黄色diff 数学(整数問題) 離散対数 考察：場合分けして考える abundanceの活用 全探索 位数の法則 そのまま覚えたいシンプル設定の中堅以上の典型問題 離散対数の verify に 問題へのリンク 問題概要 4 つの整数 が与えられる。 は素数である。 整数 が の範囲を動くときの、 を で割ったあまりの最小値を求めよ。 制約 は素数 考えたこと まず、 を満たす最小の正の整数 を求める (これを位数と呼ぶ)。これは離散対数によって求められる。 まず 以上 以下の整数の範囲内に の倍数が含まれるならば、答えは明らかに 1 である。そうでないときは、次のようにしてよい ( を で割ったときの商が等しいため)。 を % で置き換える を % で置き換える 場合分け このあとは次のように考えることができる。 が小さいとき： に対する をすべて求める… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F11%2F04%2F045400" title="AtCoder ARC 042 D - あまり (試験管黄色) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-11-04 04:54:00 rich https://drken1215.hatenablog.com/entry/2020/11/04/045400 1.0 100%