luogu 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、L，分别表示数据组数和询问类型（对于一个测试点内的所有数

据，询问类型相同）。

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

输出格式：

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

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

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

输入输出样例

输入样例#1：

输出样例#1：

2
1
2

输入样例#2：

输出样例#2：

2
1
0

输入样例#3：

输出样例#3：

0
1
Orz, I cannot find x!
0

说明

本蒟蒻调了一下午样例，一个都没过

然后交上去ac，

突然意识到windows的 lld 和 I64d似乎从来没准过，orz orz 并且快速幂不知道怎么也写炸了

第一问，水快速幂+mod

第二问，可用exgcd求，

当z为gcd（a，p）的倍数时才有解。

第三问，用bsgs(拔山盖世）求的是离散对数

具体可以自行百度。

  1 #include<cstdio>
  2 #include<map>
  3 #include<cmath>
  4 using namespace std;
  5 
  6 typedef long long LL;
  7 int T,L;
  8 
  9 LL qpow(LL a,LL p,LL mod)
 10 {
 11     LL base=a;
 12     LL sum=1;
 13     while(p!=0)
 14     {
 15         if(p&1)
 16         sum=(sum*base)%mod;
 17         base=(base*base)%mod;
 18         p>>=1;
 19     }
 20     return sum;
 21 }
 22 
 23 void work1()
 24 {
 25     LL y,z,p;
 26     scanf("%lld%lld%lld",&y,&z,&p);
 27     printf("%lld
",qpow(y,z,p)%p);
 28     return ;
 29 }
 30 
 31 
 32 void exgcd(int a,int b,LL &d,LL &x,LL &y)
 33 {
 34     if(!b){d=a;x=1;y=0;return ;}
 35     exgcd(b,a%b,d,y,x);
 36     y-=x*(a/b);
 37 }
 38 LL gcd(LL a,LL b)
 39 {
 40     if(!b) return a;
 41     return gcd(b,a%b);
 42 }
 43 void work2()
 44 {
 45     LL a,b,y,z,x,d,mod;
 46     scanf("%lld%lld%lld",&y,&z,&mod);
 47     a=y;
 48     b=-mod;
 49     d=gcd(a,b);
 50     if(z%d)
 51     {
 52         printf("Orz, I cannot find x!
");
 53         return ;
 54     }
 55     a/=d;b/=d;z/=d;
 56     exgcd(a,b,d,x,y);
 57     x*=z;x%=b;
 58     while(x<0)    x+=b;
 59     printf("%lld
",x);
 60 }
 61 
 62 
 63 map<LL,LL>mp;
 64 void work3()
 65 {
 66     mp.clear();
 67     LL y,z,q,p;
 68     scanf("%lld%lld%lld",&y,&z,&p);
 69     y%=p;
 70     if(!y&&!z)
 71     {
 72         puts("1");return ;
 73     }
 74     if(!y)
 75     {
 76         printf("Orz, I cannot find x!
");
 77         return;
 78     }
 79     LL pos=ceil(sqrt(p));
 80     LL ans;
 81     for(LL i=0;i<=pos;i++)
 82     {
 83         if(i==0)
 84         {
 85             ans=z%p;
 86             mp[ans]=1;
 87             continue;
 88         }
 89         ans=(ans*y)%p;
 90         mp[ans]=i;
 91     }
 92     ans=1;
 93     LL t=qpow(y,pos,p);
 94     for(LL i=1;i<=pos;i++)
 95     {
 96         ans=(ans*t)%p;
 97         if(mp[ans])
 98         {
 99             LL b=i*pos-mp[ans];
100             printf("%d
",(b%p+p)%p);
101             return ;
102         }
103     }
104     printf("Orz, I cannot find x!
");
105 }
106 int main()
107 {
108     scanf("%d%d",&T,&L);
109     if(L==1)
110     for(int i=1;i<=T;i++)
111     work1();
112     if(L==2)
113     for(int i=1;i<=T;i++)
114     work2();
115     if(L==3)
116     for(int i=1;i<=T;i++)
117     work3();
118     return 0;
119 }