首页 > 代码库 > P2485 [SDOI2011]计算器

P2485 [SDOI2011]计算器

2024-11-21 03:50:02   203人阅读

 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：
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. 快速幂，
  2. 求yx=z(mod p)，转化成，yx-kp = z；可以用扩展欧几里得求解，并且要求z%gcd(y,p)!=0，（扩展欧几里得求ax+by=c：http://www.cnblogs.com/MashiroSky/p/5912977.html），         补充：因为p是质数，所以可以用费马小定理， p是质数，y与p互质，所以y有逆元，x=y^(-1)*z，y^(-1)=y^(p-2)，因为0没有逆元，所以只有y=0时无解
  3. bsgs

注意，int与longlong类型，结尾的换行符

code

  1 #include<iostream>  2 #include<cstdio>  3 #include<map>  4 #include<cmath>  5   6 using namespace std;  7 typedef long long LL;  8 map<int,int>mp;  9  10 int ksm(int a,int p,int mod) 11 { 12     int now = 1; 13     while (p) 14     { 15         if (p&1) 16             now = 1ll*now*a%mod; 17         a = 1ll*a*a%mod; 18         p = p>>1; 19     } 20     return now; 21 } 22 int exgcd(int a,int b,int &x,int &y) 23 { 24     if (b==0) 25     { 26         x = 1, y = 0; 27         return a; 28     } 29     int r = exgcd(b,a%b,x,y); 30     int t = x; 31     x = y; 32     y = t-(a/b)*y; 33     return r; 34 } 35 void bsgs(int a,int b,int p) 36 { 37     int m,t,ans,now; 38     if (a%p==0&&b==0)  39     { 40         printf("1\n");return ; 41     } 42     if (a%p==0)  43     { 44         printf("Orz, I cannot find x!\n");return ; 45     } 46     mp.clear(); 47     m = ceil(sqrt(p)); 48     now = b%p; 49     mp[now] = 0; 50     for (int i=1; i<=m; ++i) 51     { 52         now = (1ll*now*a)%p; 53         mp[now] = i; 54     } 55     t = ksm(a,m,p); 56     now = 1; 57     for (int i=1; i<=m; ++i) 58     { 59         now = (1ll*now*t)%p; 60         if (mp[now]) 61         { 62             ans = i*m-mp[now]; 63             printf("%d\n",(ans%p+p)%p); 64             return ; 65         } 66     } 67     printf("Orz, I cannot find x!\n"); 68 } 69 int main() 70 { 71     int t,k,a,b,c; 72     scanf("%d%d",&t,&k); 73     if (k==1) 74     { 75         for (int i=1; i<=t; ++i) 76             scanf("%d%d%d",&a,&b,&c),printf("%d\n",ksm(a,b,c)); 77     } 78     else if (k==2) 79     { 80         int x,y; 81         for (int i=1; i<=t; ++i) 82         { 83             scanf("%d%d%d",&a,&b,&c); 84             int d = exgcd(a,c,x,y); 85             if (b%d!=0) printf("Orz, I cannot find x!\n");    //换行符  86             else  87             { 88                 x = 1ll*x*(b/d)%c; 89                 x = (x%(c/d)+c/d)%(c/d); 90                 printf("%d\n",x); 91             } 92         } 93     } 94     else 95     { 96         for (int i=1; i<=t; ++i) 97             scanf("%d%d%d",&a,&b,&c),bsgs(a,b,c); 98     } 99     return 0;100 }

 

P2485 [SDOI2011]计算器


联系
我们