ABC 401-500/ABC414E - Count A%B=C - 競技プログラミング用 知識集積所【7/13更新】

---

問題

ABC414E
ABCよりもARCっぽい……。

必要知識

B以下レベルの内容は省略

• 順列組み合わせ（未作成）
• 剰余類環

考え方

一番面倒そうな「a,b,cが相異なる」という条件をかみ砕いてみる。

まず、bとcが一致することはありえない。
余りは絶対に割る数以下だからである。

次に、aとbが一致する条件こともありえない。
その場合c=0だからである。

最後に、aとcが一致する条件を考える。
これは、bで割った商が0になる、つまりa<bという条件と同じである。

つまり、問題の条件は、「a>bであり、a%b==cである」という意味でとらえてよい。
さらに言えば、aがbの倍数でなければcは勝手に1つ決まるため、
「1<=b<a<Nであるaとbで、aがbの倍数でないものはいくつあるか」と考えてよい。

まず、b=1なのは明らかにダメなので、2以上で考えるとして、
「2以上N以下の異なる整数を2つ選ぶ(n-1)(n-2)/2通りから、aがbの倍数になってしまう個数を引くといくつか？」
を考えればよい。

aがbの倍数になってしまう個数は、愚直にやるとforループを最大10^12回回す必要があり、TLE。
そこで、min(b,a/b)がiであるものをカウントしていけば、最大でも10^6回回せば足りるので間に合う。
min(b,a/b)がiであるものの個数は、i*i<=Nの場合に

• b<a/bのものは、n/i-i個（b=iで、a=(i+1)*i,(i+2)*i,……）
• b=a/bのものは、1個（a=i*i、b=iだけ）
• b>a/bのものは、n/i-i個（b<a/bのものとswap(b,a/b)しただけなので）

の合計で2*(n/i-i)+1個ある。
それらを順次引き算していけばよい。

答えはmod998244353での値なので、剰余類環も参照。

解答例

解答例

注意点

(n-1)(n-2)/2の計算のオーバーフローに注意

nが10^12くらいあるので、そのまま計算するとlong long型でもオーバーフローする。
以下のどちらかの方法をとること。

n-1とn-2をそれぞれmod998244353にして掛け算し、さらに2^(998244353-2)を掛ける。
掛け算のたびにmod998244353する。

nが偶数なら(n-1)*{(n-2)/2}、nが奇数なら{(n-1)/2}*(n-2)、と考えて、掛け算直前に両方をmod998244353にし、掛けた後もmod998244353する。

別解