#### **ヒント**

　$U$ が定められたとします. OMC君が最適な行動をとったときの $U$ の変化の様子を考察しましょう.

<details><summary>ヒント1<\/summary>

　操作前の有理数を $u$ , 操作後の有理数を $v$ とします. $1,u,v$ の大小関係を調べましょう.

<\/details>
<details><summary>ヒント2<\/summary>

　$c(u)=b(u)-a(u)$ とします.  $u$ に対して操作を繰り返すときの $c(u)$ の変化を観察しましょう.

<\/details>
<details><summary>ヒント3<\/summary>

　$c(s)$ はいくらでしょうか？

<\/details>
<details><summary>ヒント4<\/summary>

　$c(s)=1$ です. なぜでしょうか？

<\/details>
<details><summary>ヒント5<\/summary>

　$u$ に対して操作を繰り返して初めて $c(u)=1$ となったとき, $u$ はいくらでしょうか？

<\/details>

#### **略解**

<details><summary>略解<\/summary>

　$U$ の最大値を $m$ とする. OMC君の最適な行動は, $U$ の要素をすべて以下の $s$ に一致させることである.

$$s=\dfrac{\left\lceil \dfrac{m}{1-m} \right\rceil}{\left\lceil \dfrac{1}{1-m} \right\rceil}$$

これが $m$ に関して単調増加であることから, あなたの最適な行動は $m$ を最大化することである. ここで $m$ の最大値は $\dfrac{9929}{9931}$ であるから, $s_0=\dfrac{4965}{4966}$ である. 従って, 求める値は $\bf{24656190}$ .

<\/details>

#### **解説**

　OMC君の操作について, 操作前の有理数を $u$, $1$ 回操作した後の有理数を $v$ とする. つまり

$$v=\dfrac{a(u)+1}{b(u)+1}$$

このとき $u\lt 1\implies u\lt v\lt 1$ が成り立つ.

<details><summary>証明<\/summary>

　$u\lt 1$ のとき $a(u)\lt b(u)$ である. 

　$a(u)\lt b(u)$ の両辺に $1$ を加えて $b(u)+1$ で割ると $v\lt 1$ が得られる. 

　$a(u)\lt b(u)$ の両辺に $a(u)b(u)$ を加えて $b(u)(b(u)+1)$ で割ると $u\lt v$ が得られる.

<\/details>

　従って常に $u_i\lt 1$ であり, 操作するごとに値は単調に増加する. ここで, $c(u)$ を次のように定める.

$$c(u)=b(u)-a(u)$$

このとき $c(v)\ |\ c(u)$ が成り立つ.

<details><summary>証明<\/summary>

　$g=\gcd (a(u)+1,b(u)+1)$ とする. このとき $a(v), b(v)$ は次のように表せる.
$$a(v)=\dfrac{a(u)+1}{g},\quad b(v)=\dfrac{b(u)+1}{g}$$
従って 
$$c(v)=b(v)-a(v)=\dfrac{b(u)-a(u)}{g}=\dfrac{c(u)}{g}$$
と表せ, $g$ が正整数であることから $c(v)$ は $c(u)$ を割り切り, 特に商は $g$ であることが示された. 

<\/details>

　よって $c(u)$ は操作によってその約数にしか変化しない. 特に $c(u)$ は単調に減少する.\
　さらに, 有限回の操作によって $c(u)=1$ となる.

<details><summary>証明<\/summary>

　いま $c(u)\neq 1$ とする. $u$ に対する有限回の操作によって $c(u)$ の値が減少することを示せば, それを繰り返し適用することでやはり有限回の操作によって $c(u)=1$ になることが示される. 以下, 有限回の操作によって $c(u)$ の値が減少することを背理法で示す.

　$c(u)$ が何度操作しても減少しないと仮定する. このとき $c(u)$ は一定なのでこれを $c$ とおく. また, 常に $\gcd (a(u)+1,b(u)+1)=1$ である. ところが, $1$ 度の操作につき $a(u),b(u)$ の値はちょうど $1$ ずつ増加するので, $c$ 回未満の操作の後において $a(u),b(u)$ が共に $c$ の倍数になり, これは $\gcd = 1$ に矛盾する.

<\/details>

　$U$ の要素が全て一致するならば少なくとも $c(u)$ の値が一致しなければならないが, はじめの $U$ に対する $c(u_i)$ の値たちの最大公約数は $1$ であるから, $c(s)=1$ が分かる.

<details><summary>証明<\/summary>

　はじめの $U$ に対する $c(u_i)$ たちの値は $p_{i+615}-p_i$ である. これらの最大公約数が $1$ でないとして矛盾を導く. 最大公約数が $1$ でないとき, ある素数 $p$ が存在して任意の $i$ に対して $p_{i+615}-p_i$ が $p$ の倍数となる. つねに $p_{i+615}-p_i\lt 10007$ であるから, $p\lt 10007$ である. しかしこのとき, $p_i,\ p_{i+615}$ のうちいずれか一方のみが $p$ と一致するような $i$ が唯一存在するため矛盾.

<\/details>

　ここで $u$ に対して操作を繰り返して初めて $c(u)=1$ となったときの $u$ の値を調べよう. より形式的には, 次の $d(u)$ を調べよう.

- $c(x)=1$ かつ $u$ に対して操作を繰り返して $x$ とできるような $x$ のうち最小のものを $d(u)$ とする.

　$u\le \dfrac{n}{n+1}$ となる最小の $n$ を $n_0$ とおけば

$$n_0=\left\lceil \dfrac{u}{1-u} \right\rceil$$

であるが, $u$ は操作によって単調に増加するから少なくとも $\dfrac{n_0}{n_0+1}\le d(u)$ である(*1). 実は等号が成立する(*2).

<details><summary> (*1),(*2)の補足<\/summary>

(*1)　このことはよく「自明な下界」などと表現される. 複数の条件があるとき, 考えやすいものを選んで「少なくとも〜が成り立つ」といった考察が有効な場合がある.

(*2)　このことはよく「自明な下界が達成可能」などと表現される. 必要条件を考えると実はそれが十分条件でもあった, ということはよくある. 必要条件はできるだけ強い条件にしないと十分条件にならないため, 必要条件に関する深い考察はしばしば役に立つ.

<\/details>

<details><summary>証明<\/summary>

$$a(u)(n+1)\lt b(u)n\implies a(u)(n+1)+n+1\le b(u)n+n$$

であるから

$$u\lt \dfrac{n}{n+1}\implies v\le \dfrac{n}{n+1}$$

が得られる. この式において $n=n_0$ とおけば次のことが分かる.

- $u$ が $\dfrac{n_0}{n_0+1}$ 未満だとする. 一度操作すると再び $\dfrac{n_0}{n_0+1}$ 未満であるか,または $\dfrac{n_0}{n_0+1}$ に一致する.

　従って, $u$ に対して何度か操作を行うと $\dfrac{n_0}{n_0+1}$ に一致する. よって $d(u)=\dfrac{n_0}{n_0+1}$ である.

<\/details>

　以上の考察から 

$$d(u)=\dfrac{\left\lceil \dfrac{u}{1-u} \right\rceil}{\left\lceil \dfrac{u}{1-u} \right\rceil +1}=\dfrac{\left\lceil \dfrac{u}{1-u} \right\rceil}{\left\lceil \dfrac{1}{1-u} \right\rceil}$$

が得られる. 従ってOMC君の最適な行動の一例は, まず与えられた $U$ の各要素 $u_i$ に対してそれぞれ何度か操作して $d(u_i)$ に変化させ, その後, $U$ の要素をすべて $d(u_i)$ の最大値に変化させることである. さらに $d(u)$ が $u$ に関して単調増加であることに注意すれば, はじめの $U$ の最大値を $m$ として $s$ は次で与えられることが分かる.

$$s=\dfrac{\left\lceil \dfrac{m}{1-m} \right\rceil}{\left\lceil \dfrac{1}{1-m} \right\rceil}$$

　あなたはこの $s$ を最大化するので $m$ の最大値を求めれば良い. $a(m),b(m)$ は共に素数であるから, $m$ の最大値は $\dfrac{9929}{9931}$ である (*3). このとき $s=\dfrac{4965}{4966}$ であり, 求める値は $\bf{24656190}$  である.

<details><summary> (*3)の補足<\/summary>

$$m=\dfrac{a(m)}{b(m)}=1-\dfrac{b(m)-a(m)}{b(m)}$$

と表せば, $b(m)-a(m)$ の値をできるだけ小さく, $b(m)$ をできるだけ大きくすれば良いことが分かる. 一つの発想は $a(m),b(m)$ としてできるだけ大きな**双子素数**を選ぶことであり, 本問の制約ではそれで実際 $m$ を最大化できる.

<\/details>
公式解説
https://onlinemathcontest.com/contests/omc133/editorial/5092
　正の有理数 $u$ に対して，$u=\dfrac{a}{b}$ なる互いに素な正整数 $a,b$ が一意に存在するので，このような $a,b$ をそれぞれ $a(u),b(u)$ と表します．\
　あなたとOMC君は，次で定まるルールのゲームをします.

---

【**ルール**】[$10007$ 以下の素数](https:\/\/onlinemathcontest.com\/primes)は $1230$ 個あります．まずあなたは，次の条件をみたすようにこれらを任意に $1$ 列に並べ替え，$p_1,p_2,\dots ,p_{1230}$ とします．

- $p_i\lt p_{i+615} \quad (1\le i\le 615)$

　次に，$615$ 個の正の有理数からなる数列 $U=(u_1,u_2,\dots ,u_{615})$ を，以下のように定めます．

- $u_i=\dfrac{p_i}{p_{i+615}}\quad (1\le i\le 615)$


　こうして定まった $U$ に対して，OMC君は以下の操作を $0$ 回以上行うことで，$U$ の要素をすべて同じ有理数 $s$ に一致させます．ただし，あなたの行動によらず，OMC君はこのような行動が必ず可能です．

- $1\le i\le 615$ なる $i$ をひとつ選び，$u_i$ を $\dfrac{a(u_i)+1}{b(u_i)+1}$ で置き換える．

---

　あなたは $s$ をできるだけ大きく，OMC君は $s$ をできるだけ小さくしたいです．両者が最適に行動したとき，$s$ は 
 $s_0$ になるので，$a(s_0)$ と $b(s_0)$ の**積**を求めてください.

<details><summary>OMC君の操作例<\/summary>

　$\dfrac{1}{5}$ から操作を $2$ 回すると，$\dfrac{1}{5}\longrightarrow\dfrac{1}{3}\longrightarrow\dfrac{1}{2}$ です.

<\/details>