Find All Root(extra)

2 secs 1024 MB
hide

を適当な原子根として、任意の原始根の集合は : で与えられるため、

= ( : ) - : を求めれば良いです。 前者は対数時間で、後者はの素因数を列挙したのちに、包除原理を用いて十分高速に計算できます。

計算量は です。

【余談】テストケースは全てのケースの場合ですが、これは意図的にそうしたのではなく、他のケースが見つからなかったためです。 少なくとも以下においてはそのようなケースは確認されませんでした。 これが任意の素数について成り立つかは確認できていませんので、興味のある方はぜひ真偽を確かめてください。