解説

$L(x, p)$ の $k$ 番目の数を $t$ とすると、 $|\{u \in (x, t] | gcd(u, p) = 1\} | = k$ ということである。

ここで、 $f(t) := [1, t]にあるgcd(t, p) = 1となる整数の個数$ とすると、この $f$ は明らかに単調性がある。

よって、 $f(t) - f(x) >= k$ となる $t$ の境界を二部探索で求めよう！！

さて、あとは $f$ の計算方法だが、これは素因数分解をして包除原理を使うと求めることができる。

ここの処理を雑にすると、TLEするので気をつけよう！

素因数分解は予めエラトステネスの篩の前処理を、包除原理はlcmやbitの本数の前処理をすることでTLに間に合います！！

提出コード

2200らしいがそんな難しくない。

典型を丁寧に抑えるとできる。