Educational Codeforces Round 139 (Rated for Div. 2) D. Lucky Chains

$d = y-x$ 。 $P$ を $d$ の素因数の集合とする。

$\displaystyle{ f(p) = \lceil \frac{x}{p} \rceil \times p - x }$

$\displaystyle{ \forall p \in P について \qquad min \lbrace f(p) \rbrace }$

が答え。

$x$ と $y$ は互いに素なので両方が、 $d$ の素因数 $p$ の倍数であることはない。また $d$ が $p$ の倍数なので $x$ が $p$ の倍数の場合、 $y$ も $p$ の倍数。よって $x$ と $y$ は共に $p$ の倍数ではない。
以上から $x$ と $y$ にある数 $f(p)$ を足すことで $x,y$ 両方を $p$ の倍数にできる。
$d$ のすべての素因数にたいしてこの足す数 $f(p)$ の最小値が答え。

注意点1。 $y-x=1$ のとき出力する答えは $-1$ 。「差が1の2数は互いに素 $\rightarrow$ gcd(x,y)=1」は有名事実。いくつ足しても $x$ と $y$ の差は1のままなので、永遠に互いに素。
注意点2。上の考察を素直に実装するとTLEになる。素朴に高速化するとMLEになった。いい感じに実装する必要がある。