ARC137_A – Coprime Pair

問題
感想
1. 提出
  1. 1回目

問題

A - Coprime Pair

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

感想

提出

なし

1回目

解法分からず、解説を読んだ。
問題の制約条件下では、素数の間隔は1500以下らしい。
これを知っていると、愚直な方法で解ける。
$(y-x)$が大きい方から試していく。
$(y-x)$の最大は$[L,R]$1つ、次に大きいのは2つ、というふうになっているので、最大から$K$番目に大きいものまで試すと、計算回数は$O(K^2)$。
素数判定は、大体$\log R$くらいと考えて、全体の計算量は$O(K^2 \log R)$になる。

例えば、$L=x$で、$K$番目に大きいものを試すとき、$[L,R-K], [L,R-(K+1)], … [L,R]$を試していることになる。
ここで、素数の間隔は1500以下なので、$K=1500$までに$gcd(x,y)=1$となるものがあるはず。