Educational Codeforces Round 37 - G. List Of Integers

問題リンク

解説

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に間に合います！！

提出コード

codeforces.com

まとめ

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

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