你被要求设计一个计算器完成以下三项任务:
1.给定y、z、P,计算yz mod P的值
2.给定y、z、P,计算满足xy≡z(mod P)的最小非负整数x;
3.给定y、z、P,计算满足yx≡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.要求计算yz mod P的值,可以用快速幂来 水掉 切掉,白送的20分。
2.要求计算满足xy≡z(mod P)的最小非负整数x,简单的靠细节的同余方程,用扩展欧几里得定理求x即可
3.要求计算满足yx≡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;
}
总结
这道题其实就是"超级板子结合体",加一点细节多读题多手玩数据就可以拿捏它。
细节和耐心永远是人需要且必须的