\(x^k \equiv x^{k+1} \mod N\) なる \(k\) が存在する条件を考えます。 \(N\) を素因数分解した結果を \(N=\prod p_i^{a_i}\) とします。 各 \(i\) について、\(x \equiv 1 \mod p_i^{a_i}\) もしくは \(x \equiv 0 \mod p_i\) が必要です。 どちらのケースにも当てはまらない場合、\(x^k \not \equiv x^{k+1} \mod p_i^{a_i}\) が常に成り立つため、条件を満たす \(k\) は存在しません。 またこの必要条件は十分です。 \(x \equiv 1 \mod p_i^{a_i}\) の場合は、\(x^k \equiv 1 \mod p_i^{a_i}\) が常に成立し、\(x \equiv 0 \mod p_i\) の場合は十分大きい \(k\) で常に\(x^k \equiv x^{k+1} \equiv 0 \mod p_i^{a_i}\) です。

\(f\) の値を求める範囲がちょうど \([1,N]\) なので、各 \(i\) について \(x\mod p_i^{a_i}\) を決めると対応する \(x\) がちょうど一つ存在します。

各 \(i\) について、\(\gcd(p_i^{a_i},x)=p_i^v\) での分類を考えます。 \(v\) を決め打ってみると、対応する \(x \mod p_i^{a_i}\) の個数、および \(x^k \equiv x^{k+1} \mod p_i^{a_i}\) を満たす最小の \(k\) が分かります。 \(v=0\) の時とそれ以外で、個数を求める式が異なることに注意して下さい。

各 \(i\) に対する \(v\) の決め方を全通り試せば、答えを求めることができます。 \(v\) の決め方は各 \(i\) ごとに \(a_i+1\) 通り存在するため、これらをすべてかけると \(N\) の約数の個数だけ計算することになります。

以上を実装すればこの問題が解けます。 \(N\) の素因数分解に \(O(\sqrt{N})\) 時間かけても十分間に合います。

実装例