【题目】
题目描述：
你被要求设计一个计算器完成以下三项任务：
- 给定
y
y
y、z
z
z、p
p
p，计算y
z
  m
o
d
  
p
yz\;\mathrm{mod}\; p
yzmodp 的值； - 给定
y
y
y、z
z
z、p
p
p，计算满足x
y
≡
z
(
 m
o
d
  
p
)
xy≡z(\,\mathrm{mod}\; p)
xy≡z(modp) 的最小非负整数x
x
x； - 给定
y
y
y、z
z
z、p
p
p，计算满足y
x
≡
z
(
 m
o
d
  
p
)
y^x≡z(\,\mathrm{mod}\; p)
yx≡z(modp) 的最小非负整数x
x
x。
输入格式：
输入包含多组数据。
第一行包含两个正整数
T
\mathrm T
T、
K
\mathrm K
K，分别表示数据组数和询问类型（对于一个测试点内的所有数据，询问类型相同）。
以下
T
\mathrm T
T 行每行包含三个正整数
y
y
y、
z
z
z、
p
p
p，描述一个询问。
输出格式：
对于每个询问，输出一行答案。对于询问类型
2
2
2 和
3
3
3，如果不存在满足条件的
x
x
x，则输出 “Orz, I cannot find x!”，注意逗号与 “I” 之间有一个空格。
样例数据：
【样例
1
1
1】
输入
3 1
2 1 3
2 2 3
2 3 3
输出
2
1
2
【样例
2
2
2】
输入
3 2
2 1 3
2 2 3
2 3 3
输出
2
1
0
【样例
3
3
3】
输入
4 3
2 1 3
2 2 3
2 3 3
2 4 3
输出
0
1
Orz, I cannot find x!
0
备注：
【数据范围】
对于
20
%
20\%
20% 的数据，
K
=
1
\mathrm K=1
K=1；
对于
35
%
35\%
35% 的数据，
K
=
2
\mathrm K=2
K=2；
对于
45
%
45\%
45% 的数据，
K
=
3
\mathrm K=3
K=3；
对于
100
%
100\%
100% 的数据，
1
≤
y
,
z
,
p
≤
1
0
9
1≤y,z,p≤10^9
1≤y,z,p≤109，
p
p
p 为质数，
1
≤
T
≤
10
1≤\mathrm T≤10
1≤T≤10。
【分析】
一道简单题。
对于操作
1
1
1，用快速幂轻松解决。
对于操作
2
2
2，可以先计算出
y
y
y 在模
p
p
p 意义下的逆元，然后除过去就是答案，若逆元为
0
0
0 就无解。
对于操作
3
3
3，直接套
B
S
G
S
\mathrm{BSGS}
BSGS 模板就可以了。
注意一下判无解就可以
A
\mathrm A
A 掉这道题了。
【代码】
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<tr1/unordered_map>
#define ll long long
using namespace std;
using namespace tr1;
unordered_map<int,int>Hash;
int Power(ll a,ll b,int p)
{
ll ans=1;
for(;b;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;
return ans;
}
void exgcd(int a,int b,int &x,int &y)
{
if(!b) {x=1,y=0;return;}
exgcd(b,a%b,y,x),y-=a/b*x;
}
void BSGS(int a,int b,int p)
{
Hash.clear();a%=p,b%=p;
int i,now=b,t=ceil(sqrt(p));
for(i=0;i<t;++i)
Hash[now]=i,now=(ll)now*a%p;
now=1,a=Power(a,t,p);
if(!a) return (void)puts(b?"Orz, I cannot find x!":"1");
for(i=0;i<=t;++i)
{
int j=(Hash.find(now)==Hash.end())?-1:Hash[now];
if(j>=0&&i*t-j>=0) {printf("%d\n",i*t-j);return;}
now=(ll)now*a%p;
}
puts("Orz, I cannot find x!");
}
int main()
{
int a,b,p,x,y,T,type;
scanf("%d%d",&T,&type);
while(T--)
{
scanf("%d%d%d",&a,&b,&p);
if(type==1) printf("%d\n",Power(a,b,p));
if(type==2)
{
exgcd(a,p,x,y),x=(x+p)%p;
if(x) printf("%d\n",(ll)b*x%p);
else puts("Orz, I cannot find x!");
}
if(type==3) BSGS(a,b,p);
}
return 0;
}
转载自原文链接, 如需删除请联系管理员。
原文链接：【SDOI 2011】计算器，转载请注明来源！