对于操作一,用快速幂算即可
代码如下
```cpp
int quickpow(int a,int b,int k)
{
int r=1;
while(b)
{
if(b&1) r=(r*a)%k;
b>>=1;
a=(a*a)%k;
}
return r;
}
```
对于操作二,用拓展欧几里得算法即可。
已知$a,b,n$,求$x$的最小值,使得$a*x≡b(mod p)$,可以转化为:$a*x+p*y=b$,则要求$gcd(a,n)|b$,否则无解。不定方程的求法可以参照[这道题](https://www.luogu.org/problemnew/show/P1082)
$exgcd$代码如下
```cpp
int exgcd(int a,int b,int&x,int&y)
{
if(!b)
{
x=1,y=0;
return a;
}
re int gcd=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return gcd;
}
```
对于操作三,我们需要用到一个新的算法B(拔)S(山)G(盖)S(世),他可以快速的求出求,满足$a^x ≡ b(mod p)$的最小的非负整数$x$。
求法是将$x$拆分成$i*m-j$的形式(其中$m$为$sqrt(p)$向上取整的值,则原式化为$a^{i*m-j} ≡ b(mod p)$。
移向后得$a^{i*m} ≡ b*a^j(mod p)$
我们从$0-m$枚举$j$,并将$b*a^j$的所有值存入哈希表中
接着在从$1-m$枚举$i$,算出所有的$a^{i*m}$
如果一个i对应的$a^{i*m}$的值已经在哈希表中,则表明i*m-j为一个解,输出此时的解即可
因为j<=m,所以求出的解随i的增大而减小,所以最先求出的i所对的解,即为所求。
```cpp
re int y=read(),z=read(),p=read();
re int m=ceil(sqrt(p));
if(y%p==0&&z)
{
puts("Orz, I cannot find x!");
continue;
}
//这里要特判,因为如果y%p==0了,那么不管x取何值,(y^x)%p一定为0。
a.clear();
re int now=z%p,f=quickpow(y,m,p);
a[now]=0;
for(re int i=1;i<=m;++i)
{
now=(now*y)%p;
a[now]=i;
}
now=1;
re int flag=1;
for(re int i=1;i<=m;++i)
{
now=(now*f)%p;
if(a[now])
{
re int ans=(i*m-a[now])%p;
printf("%lld\n",(ans+p)%p);
flag=0;
break;
}
}
if(flag) puts("Orz, I cannot find x!");
```
所有代码如下:
```cpp
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define debug printf("Now is Line : %d\n",__LINE__)
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define int long long
map<int,int>a;
il int read()
{
re int x=0,f=1;re char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return x*f;
}
il int quickpow(int a,int b,int k)
{
re int r=1;
while(b)
{
if(b&1) r=(r*a)%k;
b>>=1;
a=(a*a)%k;
}
return r;
}
il int exgcd(int a,int b,int&x,int&y)
{
if(!b)
{
x=1,y=0;
return a;
}
re int gcd=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return gcd;
}
signed main()
{
re int T=read(),k=read();
if(k==1)
{
while(T--)
{
re int y=read(),z=read(),p=read();
printf("%lld\n",quickpow(y,z,p));
}
}
else if(k==2)
{
while(T--)
{
re int a=read(),b=read(),p=read(),x,y;
re int gcd=exgcd(a,p,x,y);
if(b%gcd) puts("Orz, I cannot find x!");
else
{
re int temp=p/gcd;
while(x<0) x+=temp;
printf("%lld\n",((x*b/gcd)%temp+temp)%temp);
}
}
}
else
{
while(T--)
{
re int y=read(),z=read(),p=read();
re int m=ceil(sqrt(p));
if(y%p==0&&z)
{
puts("Orz, I cannot find x!");
continue;
}
a.clear();
re int now=z%p,f=quickpow(y,m,p);
a[now]=0;
for(re int i=1;i<=m;++i)
{
now=(now*y)%p;
a[now]=i;
}
now=1;
re int flag=1;
for(re int i=1;i<=m;++i)
{
now=(now*f)%p;
if(a[now])
{
re int ans=(i*m-a[now])%p;
printf("%lld\n",(ans+p)%p);
flag=0;
break;
}
}
if(flag) puts("Orz, I cannot find x!");
}
}
return 0;
}
```