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)の意味とよく使う６つの性質 | 高校数学の美しい物語
合同式とは，大雑把に言うと割り算の余りのみに注目した等式のことです。 例えば，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 の倍数のとき」と言い換えることもできます。 mod についての補足 上記の nnn のことを「法」と呼びます。 ≡\equiv≡ と mo
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
1. なぜ 1000000007 で割るのか？ 最初はこのような設問を見るとぎょっとしてしまいますが、実はとても自然な問題設定です。 $1000000007$ で割らないと、答えの桁数がとてつもなく大きくなってしまうことがあります。このとき以下のような問題が生じます: 多倍長整数がサポートされている言語とされていない言語とで有利不利が生じる 10000 桁にも及ぶような巨大な整数を扱うとなると計算時間が膨大にかかってしまう 1 番目の事情はプログラミングコンテストに特有のものと思えなくもないですが、2 番目の事情は切実です。整数の足し算や掛け算などを実施するとき、桁数があまりにも大きくなると桁数に応じた計算時間がかかってしまいます。実用的にもそのような巨大な整数を扱うときは、いくつかの素数で割ったあまりを計算しておいて、最後に中国剰余定理を適用して復元することも多いです。 なぜ 10000
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
