数学あるいはグラフの問題。

B. Moodular Arithmetic

問題

奇素数$p$と非負整数$k \lt p$が与えられる。 以下を満たす関数$f : {0,1,2,\dots,p-1} \to {0,1,2,\dots,p-1}$の数を求めよ。

  • $f(kx \bmod p) \equiv k \cdot f(x) \pmod p$

解法

$y \equiv f(x)$と$x$での値を定めると、$ky \equiv kf(x) \equiv f(kx)$と$kx$での値も定まる。 $p$は素数なので、ある$n$があって、$k^n \equiv 1 \pmod p$。$y \equiv k^ny \equiv f(k^ny) \equiv f(y)$と、一巡する。引数と値で矛盾は生じないので確認は不要。つまり、このようなサイクルの数$c$を数え、その数だけサイクルの始点の値の自由度があるため、答えは$p^c$となる。ここで$c = \frac{p-1}{n}$となる。

ただし$k = 0, 1$の場合に注意。

実装

$p$の冪乗は間に合うので線形に書いた。

#include <iostream>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
constexpr ll mod = 1000000007;
int main() {
    ll p, k; cin >> p >> k;
    ll q = 1;
    if (k != 0) {
        for (ll t = k; t != 1; t = t * k % p) ++ q;
    }
    ll result = 1;
    if (k == 1) result *= p;
    assert ((p - 1) % q == 0);
    repeat (i, (p - 1) / q) result = result * p % mod;
    cout << result << endl;
    return 0;
}