dict
2^n
orbit
(i * m + 1) % N N = 2^n
どこから始めても良いはず.
0 -> 1 -> m + 1 -> m^2 + m + 1 -> ... -> Σ[i=0->k-1] m^i (apply k-times, f^k(0)) f(x) = mx + 1
a_0 = 0 a_k = Σ[i=0->k-1] m^i (1≦k≦N-1)
a_N = 0??
m = 1 mod (m-1) m^N = ? mod N
a_p = a_q mod N <=> Σ[i=p->q-1] m^i = 0 mod N (q > p) <=> m^p Σ[i=0->q-p-1] = 0 mod N
a_p != a_q (∀p, q) => 2 !| m
assume 2 !| m a_p = a_q mod N <=> a_{q-p} = 0 mod N
a_k mod N を追えば良い.
m = 2^M ならなんでも良い!! やった分かった!!