読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #334 (Div. 1) B. Moodular Arithmetic

問題はCodeforces Round #334 (Div. 2)のD問題と同じものです。

問題文

codeforces.com

問題概要

$$ f(kx)=kf(x) $$ を満たすような有限体$\mathbb{F}_p$上の関数$f$はいくつあるか。

用語

解説に使いたいので位数という概念を導入しておく。

位数: $\mathrm{mod}\;P$で$a^x=1$となる最小の正の整数$x$を$a$の位数と呼び、$\mathrm{ord}(a)$と書く。

法が素数のときはフェルマーの小定理により、全ての元に対し位数が定まる。

解法

条件式から次のようなことが分かる。 \[ \begin{align} f(1)&=f(1) \\ f(k)&=kf(1) \\ f(k^2)&=k^2f(1) \\ f(k^3)&=k^3f(1) \\ \vdots \\ f(k^{m -1} )&=k^{m -1} f(1) \\ f(k^{m} )&=k^{m} f(1)=f(1) \\ \end{align} \]

この式を見ると、$f(1)$の値を定めれば$f(k),f(k^2),\ldots,f(k^{m -1})$の値も定まることが分かる。 このように、$f(x)$を定めれば$f(y)$も定まるような$x,y$を同じグループに入れていく。 そうすると、どのグループもサイズが$\mathrm{ord}(k)$になるので、グループの総数は$(p-1)/\mathrm{ord}(k)$になる。つまり求める答えは$p^{(p-1)/\mathrm{ord}(k)}$ 。

0だけは別に考える必要があって、$k\ne 1$のとき$f(0)=0$で、$k=1$のとき$f(0)$は任意の値を取れることに注意。

今回は$p$が小さいからゴリ押しでも位数を求められる。そもそも位数を考えなくてもグループ分けはできる。

Codeforces Round #334 (Div. 1) B. Moodular Arithme ...

感想

$p$が小さくて親切心を感じる。