Official

A - Coprime Pair Editorial by maroonrk_admin


\(\gcd(L,L+1)=1\) なので,解は必ず存在します.

\(L \leq x < y \leq R\) を満たす組 \((x,y)\) を,\((y-x)\) の大きい順に愚直に試していき,\(\gcd(x,y)=1\) だったら \((y-x)\) を出力,とすればよいです.

解法の正当性は明らかなので,計算量を見積もってみます. \(R-L\) と答えの差を \(K\) とすると,\(O(K^2)\) 個のペアを試すことになります.gcd の計算時間を考えると,計算量は全体で \(O(K^2 \log R)\) です.よって,\(K\) が小さいことが示せればよいです.

これは例えば,素数の間隔を用いると証明できます.

この問題の制約下では,\(1500\) 個の連続した整数を見れば必ずそのうちの一つは素数になっています. よって,\((x,y)=(L,R),(L,R-1),\cdots,(L,R-1500)\) を考えれば,そのうち少なくとも一つは \(\gcd(x,y)=1\) を満たすことになります. よって,\(K \leq 1500\) が示せます.

解答例(c++)

なお,実際には \(K\) はこれよりも非常に小さい値になります. \(R-5,\cdots,R\) の中に \(30\) と互いに素な数が必ず存在し,問題の制約からこれと互いに素な数が必ず \(L,\cdots,L+16\) の中に存在することが言えます.よって \(K \leq 21\) が示せます.(maspy さんによる証明) また,CRT を用いることで \(K=7\) のケースを生成することが可能です.(素数の順番をランダムシャッフルするアイディアを Nyaan さんにいただきました)

posted:
last update: