ARC 137 A - Coprime Pair

 A - Coprime Pair

問題文

整数 $L,R$ ($L < R$) が与えられます．

すぬけ君は，以下の条件を両方満たす整数の組 $(x,y)$ を探しています．

• $L \leq x < y \leq R$
• $\gcd(x,y)=1$

条件を満たす組において，$(y-x)$ がとりうる最大の値を求めてください． なお，問題の制約より，条件を満たす組が少なくとも一つ存在することが証明できます．

制約

• $1 \leq L < R \leq 10^{18}$
• 入力される値はすべて整数

---

入力

入力は以下の形式で標準入力から与えられる．

$L$ $R$

出力

答えを出力せよ．

---

入力例 1 Copy

Copy

2 4

出力例 1 Copy

Copy

1

$(x,y)=(2,4)$ とすると，$\gcd(x,y)=2$ となってしまい，条件を満たしません． $(x,y)=(2,3)$ とすれば条件を満たし，このとき $(y-x)$ の値は $1$ です． $(y-x)$ の値がこれより大きくなることはないため，答えは $1$ です．

---

入力例 2 Copy

Copy

14 21

出力例 2 Copy

Copy

5

---

入力例 3 Copy

Copy

1 100

出力例 3 Copy

Copy

99

	void solve() {
	// input
	ll r, l;
	cin >> l >> r;
	ll ans = 1LL;
	// prime number must be found in 1500
	int d = 1500;
	for (int i = 0; i <= d; i++) {
	for (int j = 0; j <= d; j++) {
	if (gcd(l + i, r - j) < 2) chmax(ans, r - j - (l + i));
	}
	}
	out(ans);
	}

view raw A - Coprime Pair.cpp hosted with ❤ by GitHub