P2485 [SDOI2011]计算器

题目描述

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

1、给定y、z、p,计算y^z mod p 的值;

2、给定y、z、p,计算满足xy ≡z的最小非负整数x;

3、给定y、z、p,计算满足y^x ≡z的最小非负整数x。

为了拿到奖品,全力以赴吧!

输入输出格式

输入格式:

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

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

据,询问类型相同)。

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

输出格式:

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

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

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

输入输出样例

输入样例#1:

3 12 1 32 2 32 3 3

输出样例#1:

212

输入样例#2:

3 22 1 32 2 32 3 3

输出样例#2:

210

输入样例#3:

4 32 1 32 2 32 3 32 4 3

输出样例#3:

01Orz, I cannot find x!0

说明

图片 1

思路:

第一问:裸快速幂

第二问:费马小定理 或者
扩展欧几里得(解ax ≡ c

第三问:裸BSGS

对于orz的判读

首先我们把上来先把y%p,把等式的左边化成最简形式

对于第二问:先z%p,把等式右边化成最简形式,在这种条件下,如果y==0&&z!=0的情况下
y%b一定等于0而不可能等于z

对于第三问:如果y%p==0无解,因为费马小定理的条件是y与p互素

为了方便理解,我把题目中的变量p改成了mod

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<map> 6 using namespace std; 7 typedef long long LL; 8 LL n,how,y,z,p; 9 map<LL,LL>mp;10 LL fastpow(LL a,LL p,LL mod)11 {12     LL base=a;LL ans=1;13     while(p!=0)14     {15         if(p%2==1)ans=(ans*base)%mod;16         base=(base*base)%mod;17         p=p/2;18     }19     return ans;20 }21 void bsgs(LL y,LL z,LL mod)22 {23     mp.clear();24     if(y%mod==0)25     {26         printf("Orz, I cannot find x!\n");27         return ;28     }29     LL m=ceil);30     LL ans;31     for(LL j=0;j<=m;j++)32     {33         if(j==0)34         {35             ans=z%mod;36             mp[ans]=1;37             continue;38         }39         ans=%mod;40         mp[ans]=j;41     }42     ans=1;43     LL t=fastpow;44     for(LL i=1;i<=m;i++)45     {46         ans=%mod;47         if48         {49             LL out=i*m-mp[ans];50             printf("%d\n",(out%mod+mod)%mod);51             return ;52         }53     }54     printf("Orz, I cannot find x!\n");55         56 }57 int main()58 {59     scanf("%d%d",&n,&how);60     while(n--)61     {62         scanf("%d%d%d",&y,&z,&p);63         y=y%p;64         if(how==1)65         printf("%d\n",fastpow;66         else if(how==2)67         {68             z%=p;69             if(y==0&&z!=0)70             printf("Orz, I cannot find x!\n");71             else72             printf("%d\n",*(fastpow(y,p-2,p))%p)%p);73         }74         else if(how==3)75         bsgs;76     }77     return 0;78 }

相关文章