题意:

给你一个方程,方程太变态不打,给你一个p一个k,p保证是大于等于3的质数,k保证在0~p-1之间的整数。要求对应函数的定义域在0~p-1值域为0~p-1的子集,求这样的函数有多少个...

分析:

【今天刚迷迷糊糊听了节集合论,做着做着就发现好像是循环群还是啥==】

k=0时,不难发现f(0)=0,其他任意。

k=1时,f(0)=f(0) mod p,发现除了其他任意外f(0)也任意。

当k>=2时,发现某规律...

不难发现假如k=2,则f(2)根据f(1),f(4)根据f(2)...以此类推,直到mod运算之后再次成为1...

所以很多组的值是根据其中某一个函数的值的变化而变化...所以发现了某规律(应该是可以证明推导的)

规律是这样的,发现<k>(这个符号的解释看离散数学==)的阶数就是将定义域划分的依据(这个应该是可以通过某著名定理推导出来,屌丝只是发现规律了)...

好的,最后这道题变成一道规律题了(学渣痛痛痛)

除了0外,定义域可以划分成w组,每组里边有<k>的阶个数字。剩下的事情就是排列组合一下,写一个快速幂求解...

反思:

这题反映了我这种学渣分析问题不全面,虽然1A但是交了之后才发现有个地方的验证自己忽略了...

代码:

#include<stdio.h>
int main()
{
int p,k;
int n=1e9+;
scanf("%d%d",&p,&k);
if(k==)
{
long long tmp=p,r=;
p--;
while(p)
{
if(p&)
{
r=r*tmp%n;
}
tmp=tmp*tmp%n;
p>>=;
}
printf("%I64d\n",r);
}
else if(k==)
{
long long tmp=p,r=;
while(p)
{
if(p&)
{
r=r*tmp%n;
}
tmp=tmp*tmp%n;
p>>=;
}
printf("%I64d\n",r);
}
else
{
long long tmp=;
long long ans;
for(int i=;;i++)
{
tmp=(tmp*k)%p;
if(tmp==)
{
ans=i;
break;
}
}
long long r=;
tmp=p;
p=(p-)/ans;
while(p)
{
if(p&)
{
r=r*tmp%n;
}
tmp=tmp*tmp%n;
p>>=;
}
printf("%I64d\n",r);
}
}
05-08 08:09