Find All Root(extra)

2 secs 1024 MB
hide's icon hide

rrを適当な原子根として、任意の原始根の集合は(( ri(modp)r^i(mod p) : 1ip11 \le i \le p - 1 ,, gcd(p1,i)=1gcd(p - 1,i) = 1 ))で与えられるため、

ansans = sumsum(ri(modp)r^i(mod p) : 1ip11 \le i \le p - 1) - sum(sum( ri(modp)r^i(mod p) : 1ip11 \le i \le p - 1 ,, gcd(p1,i)>1gcd(p - 1,i) > 1 )) modPmod P を求めれば良いです。 前者は対数時間で、後者はP1P -1の素因数を列挙したのちに、包除原理を用いて十分高速に計算できます。

計算量はO(P+2(P1の素因数の個数)log(P))O(\sqrt P + 2^{(P-1の素因数の個数)}* log(P)) です。

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