你被要求设计一个计算器完成以下三项任务：
1.给定y、z、P，计算y^z mod P的值
2.给定y、z、P，计算满足xy≡z(mod P)的最小非负整数x；
3.给定y、z、P，计算满足y^x≡z(mod P)的最小非负整数x。

输入

第一行包含两个正整数T，K
分别表示数据组数和询问类型-对于一个测试点内的所有数据，询问类型相同。

输出

对于每个询问，输出一行答案。
对于询问类型2和3，如果不存在满足条件的x，则输出"Orz, I cannot find x!"。

数据范围

20%，k=1
35%，k=2
45%，k=3
100%，1≤y,z,P≤10^9，P为质数，1≤T≤10

思路

1.要求计算y^z mod P的值，可以用快速幂来水掉切掉，白送的20分。
2.要求计算满足xy≡z(mod P)的最小非负整数x，简单的靠细节的同余方程，用扩展欧几里得定理求x即可
3.要求计算满足y^x≡z(mod P)的最小非负整数x，这就得用到bsgs算法，专克次方，详情请见bsgs.

代码实现

1.快速幂：

函数：

int qpow(int a,int p,int mod)
{
	int t=1,x=a%mod;
	while(p)
	{
		if(p&1)
		{
			t=t*x%mod;
		}
		x=x*x%mod;
		p>>=1;
	}
	return t;
}

调用：

[略]

2.扩展欧几里得求最小解：

函数：

int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	int g=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return g;
}

调用：

if(k==2)
{
	int d=exgcd(y,p,x,y);
	if(z%d!=0)
	{
		cout<<"Orz, I cannot find x!\n";
	}
	else
	{
		x=(x*z%(p/d)+p/d)%(p/d);
		cout<<x<<endl;
	}
	continue;
}

3.Bsgs：

函数：

map<int,int> mp;
int bsgs(int a,int b,int mod)
{
	mp.clear();
	if(!a)
	{
		if(!b)
		{
			return 1;
		}
		else
		{
			return -1;
		}
	}
	if(b==1)
	{
		return 0;
	}
	int bs=ceil(sqrt(mod)),ans1=1;
	for(int i=0;i<bs;i++)
	{
		mp[ans1]=i;
		ans1=ans1*a%mod;
	}
	int ans2=qpow(a,bs,mod),ans3=ans2*qpow(b,mod-2,mod)%mod;
	for(int i=1;i<=bs;i++)
	{
		if(mp[ans3]!=0)
		{
			return bs*i-mp[ans3];
		}
		ans3=ans3*ans2%mod;
	}
	return -1;
}

调用：

if(k==3)
{
	if(bsgs(y%p,z%p,p)==-1)
	{
		cout<<"Orz, I cannot find x!\n";
	}
	else
	{
		cout<<bsgs(y%p,z%p,p)<<endl;
	}
}

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t,k,x,y;
int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	int g=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return g;
}
int qpow(int a,int p,int mod)
{
	int t=1,x=a%mod;
	while(p)
	{
		if(p&1)
		{
			t=t*x%mod;
		}
		x=x*x%mod;
		p>>=1;
	}
	return t;
}
map<int,int> mp;
int bsgs(int a,int b,int mod)
{
	mp.clear();
	if(!a)
	{
		if(!b)
		{
			return 1;
		}
		else
		{
			return -1;
		}
	}
	if(b==1)
	{
		return 0;
	}
	int bs=ceil(sqrt(mod)),ans1=1;
	for(int i=0;i<bs;i++)
	{
		mp[ans1]=i;
		ans1=ans1*a%mod;
	}
	int ans2=qpow(a,bs,mod),ans3=ans2*qpow(b,mod-2,mod)%mod;
	for(int i=1;i<=bs;i++)
	{
		if(mp[ans3]!=0)
		{
			return bs*i-mp[ans3];
		}
		ans3=ans3*ans2%mod;
	}
	return -1;
}
signed main()
{
	cin>>t>>k;
	while(t--)
	{
		int y,z,p;
		cin>>y>>z>>p;
		if(k==1)
		{
			cout<<qpow(y,z,p)<<endl;
			continue;
		}
		if(k==2)
		{
			int d=exgcd(y,p,x,y);
			if(z%d!=0)
			{
				cout<<"Orz, I cannot find x!\n";
			}
			else
			{
				x=(x*z%(p/d)+p/d)%(p/d);
				cout<<x<<endl;
			}
			continue;
		}
		if(k==3)
		{
			if(bsgs(y%p,z%p,p)==-1)
			{
				cout<<"Orz, I cannot find x!\n";
			}
			else
			{
				cout<<bsgs(y%p,z%p,p)<<endl;
			}
		}
	}
	return 0;
}