# BZOJ2242 计算器

#### 题目大意

1. 给定y,z,p,计算Y^Z Mod P 的值；
2. 给定y,z,p，计算满足xy≡ z ( mod P )的最小非负整数；
3. 给定y,z,p，计算满足y^x ≡ z ( mod P)的最小非负整数。

#### Solution

$y^x=y^{im-j}\equiv z(mod p)$即$y^{im} \equiv zy^j (mod p)$

##### Code

#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
map<ll,ll>Map;
ll ksm(ll a,ll b,ll mo1)
{
ll ans=1,tmp=a%mo1;
while (b)
{
if (b&1) ans=ans*tmp%mo1;
tmp=tmp*tmp%mo1;
b>>=1;
}
return ans;
}
ll exgcd(ll n,ll m,ll &x,ll &y)
{
if (!m)
{
x=1,y=0;
return n;
}
ll g=exgcd(m,n%m,x,y);
ll t=x;
x=y,y=t-n/m*y;
return g;
}
int main()
{
int cas,type;
scanf("%d%d",&cas,&type);
while (cas--)
{
ll a,b,p;
scanf("%lld%lld%lld",&a,&b,&p);
if (type==1)
{
printf("%lld\n",ksm(a,b,p));
}
if (type==2)
{
ll x,y;
ll g=exgcd(a,p,x,y);
if (b%g)
{
puts("Orz, I cannot find x!");
continue;
}
a/=g,b/=g,p/=g;
exgcd(a,p,x,y);
x=(x%p+p)%p;
x=x*b%p;
printf("%lld\n",x);
}
if (type==3)
{
if (a%p==0)
{
if (b%p==0) puts("1");
else if (b%p==1) puts("0");
else puts("Orz, I cannot find x!");
continue;
}
Map.clear();
int m=sqrt(p)+1;
ll xx=1;
Map[b%p]=1;
for (int i=1;i<=m;i++)
{
(xx*=a)%=p;
Map[xx*b%p]=i+1;
}
xx=ksm(a,m,p);
ll x1=1,ans=1LL<<50;
for (int i=1;i<=m;i++)
{
(x1*=xx)%=p;
if (Map[x1])
{
ans=min(ans,(((ll)i*m-Map[x1]+1)%(p-1)+(p-1))%(p-1));
}
}
if (ans<p) printf("%lld\n",ans);
else puts("Orz, I cannot find x!");
}
}
return 0;
}

### 4 thoughts on “BZOJ2242 计算器”

1. I have to express appreciation to the writer just for bailing me out of this condition. As a result of surfing throughout the the web and getting concepts which were not helpful, I believed my life was over. Existing without the presence of strategies to the problems you’ve solved by way of the guideline is a critical case, as well as the kind which might have in a negative way damaged my entire career if I had not discovered your website. That capability and kindness in taking care of the whole thing was important. I am not sure what I would’ve done if I hadn’t come across such a thing like this. I can now look ahead to my future. Thanks very much for your reliable and sensible guide. I will not think twice to refer your blog to any person who should have care on this matter.

2. A lot of thanks for all of your efforts on this web page. Gloria really loves going through research and it is simple to grasp why. All of us notice all of the lively method you give rewarding suggestions via this web site and even increase contribution from other people on this subject so my daughter is always starting to learn a lot. Take pleasure in the remaining portion of the year. You are always conducting a fantastic job.