codeforces #334 div 2 D.Moodular Arithmetic

2015年12月22日 0 作者 CrazyKK

http://codeforces.com/contest/604/problem/D
题意:一个恒等式 f(k*x%p)=k*f(x)%p ,k,p为常数,且满足x对于定义域为0..p-1的p的整数,值域也在0..p-1范围(不一定一一对应)。问满足题意的f有多少个。
思路:
f(0)=0,对于其他的值,当f(x)确定时,f(k*x%p)也随之确定,那么把k*x%p看做新的x,f(k*k*x%p)也随之确定…相当于【1,p-1】被分为r个小环,确定每个环可以任选一个数字,ans=p^r。环的个数可以用dfs跑一遍得到r.
注意当k=1的时候是特殊情况,f(x)恒等于f(x)那么答案应该有p的p次方种。因为对于p个f(0..p-1),每一个都可以任意取p种值。