Kazun の競プロ記録

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

AtCoder Regular Contest 137 A問題 Coprime Pair

AtCoder ARC ARC137 A問題 300 pts

問題

提出解答

問題の概要

$\displaystyle \max_{\substack{L \leq x \lt y \leq R \\ \gcd(x,y)=1}} (y-x)$

を求めよ.

制約

$1 \leq L \lt R \leq 10^{18}$

解法

素数の間隔 - Wikipedia

このサイトによると, $10^{18}$ 以下において, 素数の間隔は高々 $1500$ である.

ここで, $R-L+1$ 以下の最大の素数を $P$ とすると, $L,L+1, \dots, R$ の中に $P$ の倍数でない整数 $X$ が存在して, $\gcd(X,X+P)=1$ である.

よって, 答えは $P$ 以上であることがわかったので, $k=P, P+1, \dots, R-L+1$ において, $\gcd(x,x+k)=1$ となる $L \leq x \leq R-k$ が存在するかどうかを見れば良い.

計算量については $O((R-L+1-P)^2 \log R)$ だが, $R-L+1-P \leq 1500$ より高速である.