2017-10-16から1日間の記事一覧

POJ 1284: Primitive Roots

http://poj.org/problem?id=1284答えはφ(p-1)個になります。証明しましょう。準備.n(|p-1)についてx^n≡1(modp)はちょうどn個の解を持つ。証明.p-1=nkとしたとき、 x^(p-1)-1=(x^n-1)(x^(n(k-1))+x^(n(k-1)-1)+...+1)であり、 x^(p-1)-1≡0(modp)の解はp-1=nk…