P2485 [SDOI2011]计算器

题目描述

你被要求设计一个计算器完成以下三项任务：

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。

为了拿到奖品，全力以赴吧！

输入输出格式

输入格式：

输入文件calc.in 包含多组数据。

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

据，询问类型相同）。

以下T 行每行包含三个正整数y、z、p，描述一个询问。

输出格式：

输出文件calc.out 包括T 行.

对于每个询问，输出一行答案。

对于询问类型2 和3，如果不存在满足条件的，则输出“Orz, I cannot find x!”。

说明：

T1快速幂

T2逆元orexgcd

无解看看y可不可以整除p

T3 bsgs

从算法竞赛进阶指南上学习的，注意点写了注释

Code:

#include 
    
     #include 
     
      #include 
      #define ll long longll quickpow(ll d,ll k,ll p){    ll f=1;    while(k)    {        if(k&1) f=f*d%p;        d=d*d%p;        k>>=1;    }    return f;}ll work1(ll y,ll z,ll p){    return quickpow(y,z,p);}ll work2(ll y,ll z,ll p)//xy=z mod p{    if(y%p==0&&z!=0) return -1;    return z*quickpow(y,p-2,p)%p;}std::map 
       
         Hash;ll work3(ll y,ll z,ll p)//y^x=z mod p{    Hash.clear();//清空    z%=p;//注意先取膜    ll t=sqrt(p)+1;//注意向上取整    for(ll i=0;i
        
         =0&&~j)//试试 2 2 3这样的情况？            return i*t-j;    }    return -1;}int main(){    int t,k;    scanf("%d%d",&t,&k);    while(t--)    {        ll y,z,p;        scanf("%lld%lld%lld",&y,&z,&p);        if(k==1) printf("%lld\n",work1(y,z,p));        else if(k==2)        {            ll ans=work2(y,z,p);            if(~ans) printf("%lld\n",ans);            else printf("Orz, I cannot find x!\n");        }        else        {            ll ans=work3(y,z,p);            if(~ans) printf("%lld\n",ans);            else printf("Orz, I cannot find x!\n");        }    }    return 0;}