Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 266 B問題 Modulo Number

AtCoder ABC266 ABC B問題 200 pts

問題

提出解答

問題の概要

以下を満たす $0$ 以上 $998244352$ 以下の整数 $x$ を求めよ.

$N-x$ が $998244353$ の倍数

制約

$-10^{18} \leq N \leq 10^{18}$

解法

一般的に, 以下が成り立つ.

整数 $a,b$ と正の整数 $m$ に対して, 以下は同値である.

$a-b$ は $m$ の倍数である.
$a,b$ を $m$ で割った余りが等しい.

よって, $x$ は $N$ を $998244353$ で割った余りである. 実はこれ以外に条件を満たす整数は存在しない.