問題概要

問題へのリンク

整数 $N \geq 1$ と，整数の multiset $ A, B$ が与えられる．$A$, $B$ の要素数は $N$ である． 整数 $K$ で，multiset $ \{ a \bmod K \mid a \in A \}$ が $B$ と等しくなるものがあるか判定し， あれば1つ与えよ．

制約

$1 \leq N \leq 10^4$，$0 \leq a_i, b_i \leq 10^6$

解

tutorialへのリンク

略解．click to open

そういう $K$ があれば $K$ は，$d := \sum_i a_i - \sum_i b_i$ の約数になる． ($10^{10}$ 以下の数の約数の個数の最大値は $2304$ 個である．)