競技プログラミング用 知識集積所
ABC460E - x ＋ y ≡ x ＋ y
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
数学問題。
yの桁数がd桁だとすると、条件は 10^d*x+y≡x+y つまり (10^d-1)x≡0 である。
よって、実はyの値そのものはあまり関係なく、d桁であるものが何個あるかだけが重要。
よって、実はyの値そのものはあまり関係なく、d桁であるものが何個あるかだけが重要。
さて、(10^d-1)*xをmで割れるか考えたいが、そのままやるとオーバーフローする。
そこで、(10^d-1)とmの最大公約数gを出し、xを(m/g)で割れるかのチェックという形にする。
そこで、(10^d-1)とmの最大公約数gを出し、xを(m/g)で割れるかのチェックという形にする。
1以上n以下の整数xについて、(m/g)で割り切れる個数はn/(m/g)である。
これにd桁になるようなyの個数を掛けると、yがd桁であるような(x,y)の個数がわかる。
それをdごとに求めて総和を取ればよい。
これにd桁になるようなyの個数を掛けると、yがd桁であるような(x,y)の個数がわかる。
それをdごとに求めて総和を取ればよい。
答えは998244353で割った余りを要求されているので、剰余類環の考えに従って処理する。
解答例
注意点
unsigned long long型※を使用する。
N<10^18だったらよかったのだが、N<=10^18にされているせいで10^19を取り扱う必要がある。
これはlong long型ですら収まらない。
unsigned long long型※なら1.8*10^19まで扱えるので、うっかり足し算しないように気を付ければギリギリ足りる。
これはlong long型ですら収まらない。
unsigned long long型※なら1.8*10^19まで扱えるので、うっかり足し算しないように気を付ければギリギリ足りる。
