競技プログラミング用 知識集積所
ABC448E - Simple Division
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
考察問題、というか数学問題。
まず、ランレングス圧縮※された数値を扱う方法。
これは、下からi+1桁目からj桁目までcが並んでいる場合、その部分の値はc*(10^j-10^i)/9である。
ということは、9Nを考えるなら、c*(10^j-10^i)の総和を考えればいいので、2N個程度の10の累乗×1桁の総和として表現できる。
特に、ある数を法とした剰余類環での値を求めるだけなら、繰り返し二乗法※を用いることで1つ1つを桁数のlogくらいで求めることができ、十分高速。
これは、下からi+1桁目からj桁目までcが並んでいる場合、その部分の値はc*(10^j-10^i)/9である。
ということは、9Nを考えるなら、c*(10^j-10^i)の総和を考えればいいので、2N個程度の10の累乗×1桁の総和として表現できる。
特に、ある数を法とした剰余類環での値を求めるだけなら、繰り返し二乗法※を用いることで1つ1つを桁数のlogくらいで求めることができ、十分高速。
NをMで割った商を10007で割った商をQ、NをMで割った商を10007で割った余りをR、NをMで割った余りをSとすると、
N = M * (10007Q+R) + S
となる。
これは変形すると
これは変形すると
N = 10007MQ + (MR+S)
となる。
Rは10007未満、SはM未満なので、Rの値は「Nを10007Mで割った余りをMで割った余り」として求めることもできる。
Rは10007未満、SはM未満なので、Rの値は「Nを10007Mで割った余りをMで割った余り」として求めることもできる。
両者を合わせると、
9N = 90063MQ + (9MR+9S)
と考えて、「9Nを90063Mで割った余りを9Mで割った余り」とすれば、この問題を解くことができる。
