AtCoder ABC 164 D - Multiple of 2019 (水色, 400 点) - けんちょんの競プロ精進記録
まさかの既出！！！しかも割と最近の ABC-E！！！ drken1215.hatenablog.com 問題へのリンク 問題概要 から までの数字のみからなる文字列 が与えられる。 の連続する区間であって、 の倍数であるものが何個あるのかを求めよ。 制約 考えたこと 実は完全にマジで既出だった！！！！！ ただし ABC 157-E では、「2019」のところが一般的な素数 なので、ちょっとだけコーナーケースを含んで難しくなってる。今回の問題では、 が なので、少しだけ簡単になってる。 drken1215.hatenablog.com さて、そもそもこの問題のように、「連続する区間」についての問題では、"累積和的なもの" をとるのが定石である。通常、累積和は左側から考えるケースが多いけど、今回は右側から考える。 たとえば 8 桁の整数 S = 41817134 について考えてみる。これの部分
AtCoder ABC 158 E - Divisible Substring (青色, 500 点) - けんちょんの競プロ精進記録
こういう問題を求めてた！！ 問題へのリンク 類題として、こんなのがある。 drken1215.hatenablog.com 問題概要 長さ の、各文字が '0'〜'9' のいずれかとなっている文字列 と、素数 が与えられる。 の空でない連続する区間であって、その整数が で割り切れるものが何個あるかを求めよ。 制約 は を満たす素数 考えたこと 文字列の右側から 個分からなる整数を とおくことにする。たとえば、 S = 1533032 であれば、 = 0 = 2 = 32 = 32 ("032") = 3032 という感じにする。こういう風に「区間に関する問題において、累積和的なものを考える」というのは、Zero-Sum Ranges でもおなじみの考え方！！！！！！！ さて、このとき、S の区間 が条件を満たす条件は と表せることになる。ここで勢いで両辺に をかけて という風にしてしまいた
ユークリッドの互除法の証明と不定方程式 | 高校数学の美しい物語
ユークリッドの互除法を使って 390390390 と 273273273 の最大公約数を計算してみましょう。 まず，390390390 を 273273273 で割ると，商が 111 で余りが 117117117 です： 390=273×1+117390=273\times 1+117390=273×1+117 よって，重要な性質 より 「390390390 と 273273273 の最大公約数」 ＝「273273273 と 117117117 の最大公約数」 次に，273273273 を 117117117 で割ります： 273=117×2+39273=117\times 2+39273=117×2+39 よって，重要な性質 より 「273273273 と 117117117 の最大公約数」 ＝「117117117 と 393939 の最大公約数」 次に，117117117 を 3939
合同式(mod)の意味とよく使う６つの性質 | 高校数学の美しい物語
合同式について，意味・性質・何の役に立つのか，などを整理しました。これを読めば数学における「mod」という記号の意味がわかります。 合同式とは，大雑把に言うと割り算の余りのみに注目した等式のことです。 例えば，777 と 444 はどちらも 333 で割った余りが 111 です。これを，合同式では 7≡4(mod3)7\equiv 4 \pmod{3}7≡4(mod3) と書きます。 上の合同式は「7合同4モッド3」と読みます。 777 と 444 は 333 で割った余りのみに注目すれば同じという意味です。 より一般に，aaa と bbb を nnn で割った余りが等しいとき，合同式では a≡b(modn)a\equiv b\pmod{n}a≡b(modn) と書きます。なお，「aaa と bbb を nnn で割った余りが等しいとき」という条件は「a−ba-ba−b が nnn の倍数
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://pc1.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2016/05.pdf
https://pc1.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2011/05.pdf
