By

文章目录
  1. 1. 题意
  2. 2. 分析

原题

题意

给定p和k，p是大于2的素数。找满足f(kx mod p)=k*f(x) mod p的方案数，其中f(1,2,3,4……p-1)->{1,2,3,4……p-1}.

例如p=3,k=2的方案数有三种：

f(0) = 0, f(1) = 1, f(2) = 2.  
f(0) = 0, f(1) = 2, f(2) = 1.  
f(0) = f(1) = f(2) = 0.

分析

当p=3,k=2的时候：

2*f(0)%3=f(0)=f(2*0%3)
2*f(1)%3=f(2)=f(2*1%3)
2*f(2)%3=f(1)=f(2*2%3)

所以：
0->0
1->2->1
2->1->2
这题主要应用了群的性质，除去0的模p运算，是一个群
先不考虑0，让x和k都非0
我们先证明k * x % p的值各不相同，且会包含全部的1~p-1

假设k * x1 % p = k * x2 % p ,且x1 != x2
在群中，所以每个元素有逆元，那么k^-1 * k * x1 %p = k^-1 * k * x2 %p
所以x1 = x2，由此得证。

利用不停迭代，可以得出下面的关系：

任取x1，有f(x1) = k*f(x2)%p = k^f(k*f(x3)) % p =k^2*f(x2)%p= … = k^l * f(x1)

x1 到 xl就凑成了一个循环的集合，确定x1，则其它元素的值都被确定了，所以对这样一个集合有f(x1)可以为0~p-1的任意值，所以有p种选择，所以找到所有这样的集合个数num，则ans = p ^ num
如何找到集合个数呢，我用的方法是用x1推xl，xl推xl-1，直到循环，xl = k * x1 % p
现在把0加回来，对于k可以特判k=0时，有p^p-1种，k=1时，有p^p种。
当k>1时，对于x=0时，我们固定让f(x) = 1，其它值有上述算法即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
const long long MOD=1e9+7;
int main()
{
    long long p,k,temp,ans,num;
    while(scanf("%I64d%I64d",&p,&k)!=EOF){
        if(k==0){
            num=p-1;
        }
        else if(k==1){
            num=p;
        }
        else{
            int i;
            int temp;
            temp=k;
            for(i=1;;i++){
                if(temp==1){
                    break;
                }
                else{
                    temp=(temp*k)%p;
                }
            }
            num=(p-1)/i;
        }
        ans=1;
        for(int i=0;i<num;i++){
            ans=(ans*p)%MOD;
        }
        printf("%I64d\n",ans);
    }
}
文章目录
  1. 1. 题意
  2. 2. 分析