問題概要
$N \ $以下の正整数のうち、$M \ $の倍数であるものの総和を$ \ 998244353 \ $で割った余りを求めよ。
制約
- $1 \leq N \leq 10^{18}$
- $1 \leq M \leq N$
解説
求める値は初項$ \ 0 \ $、末項$ \ [ \frac{N}{M} ] \times M \ $、公差$ \ M \ $、項数を$ \ [ \frac{N}{M} ] + 1 \ $とした等差数列の総和であると言えます。 この数列は$ \ 0,M,2M,3M,\ldots \ $と表せます。
末項を$ \ kM \ $とすると、数列は$ \ 0,M,2M,\ldots,kM \ $となり、この数列を反転させて元の数列に足すと$ \ 0 + kM,M + ( k - 1 ) M, 2M + (k-2)M,\ldots,kM + 0 = kM,kM,kM,\ldots,kM \ $となります。 よって、これらの総和は$ \ \frac{末項 \times (項数)}{2} \ $で求められます。
