BZOJ2242 [SDOI2011]计算器【BSGS】-白红宇

BZOJ2242 [SDOI2011]计算器【BSGS】

阅读量：4925 次

发布时间：2019-06-11

本文共 2829 字，大约阅读时间需要 9 分钟。

2242: [SDOI2011]计算器

Time Limit: 10 Sec

Memory Limit: 512 MB

Submit: 4741

Solved: 1796

[ ][ ][ ]

Description

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

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)的最小非负整数。

Input

输入包含多组数据。

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

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

Output

对于每个询问，输出一行答案。对于询问类型2和3，如果不存在满足条件的，则输出“Orz, I cannot find x!”，注意逗号与“I”之间有一个空格。

Sample Input

【样例输入1】
3 1
2 1 3
2 2 3
2 3 3
【样例输入2】
3 2
2 1 3
2 2 3
2 3 3
【数据规模和约定】
对于100%的数据，1<=y,z,p<=10^9，为质数，1<=T<=10。

Sample Output

【样例输出1】
2
1
2
【样例输出2】
2
1
0

K = 1 快速幂

K = 2 exgcd

K = 3 BSGS

前两个就不说了

我们讲讲BSGS【大步小步法】

对于a^x≡b (mod p)

我们设x = i * m - j，【m = √p】

就有(a ^ m) ^ i ≡ b * (a ^ j) (mod p)

j的取值是[0,m-1]，i的取值是[1,m]【费马小定理,x一定小于等于p - 1】

我们枚举j放入哈希表，再枚举i，查找有没有对应的j

由于i由小枚举，保证了i * m最小

由于j由小枚举，大的会覆盖小的，所以保证了-j最小

最后的x一定是最小的

什么时候会无解呢？

无解充要条件：gcd(a,p) != 1，且b mod p != 0，也就是a,p不互质

证明：首先p规定是质数了，a与p不互质当且仅当a是p的倍数，此时a mod p = 0,除非b也是p的倍数，否则无解

BSGS算法主要在于减少枚举量，将枚举分解到两侧去，以实现时间的优化

#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #define LL long long int#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<
           
            <<' '; puts("");using namespace std;const int maxn = 100005,maxm = 100005,INF = 1000000000;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}int T;LL P;map
            
              s;LL qpow(LL a,LL b){ LL ans = 1; for (; b; b >>= 1,a = a * a % P) if (b & 1) ans = ans * a % P; return ans % P;}void exgcd(LL a,LL b,LL& d,LL& x,LL& y){ if (!b){x = 1; y = 0; d = a;} else exgcd(b,a % b,d,y,x),y -= (a / b) * x;}void solve1(){ LL a,b; while (T--){ a = read(); b = read(); P = read(); printf("%lld\n",qpow(a,b)); }}void solve2(){ LL a,c,b,d,x,y,b0; while (T--){ a = read(); c = read(); b = read(); exgcd(a,b,d,x,y); if (c % d != 0) puts("Orz, I cannot find x!"); else { x *= c / d; b0 = b / d; printf("%lld\n",(x % b0 + b0) % b0); } }}void solve3(){ LL a,b,m,ans,t; while (T--){ a = read(); b = read(); P = read(); ans = -1; s.clear(); m = (LL)sqrt(P); t = qpow(a,m); if (a % P == 0){ if (b % P == 0) puts("1"); else puts("Orz, I cannot find x!"); continue; } for (LL i = 0; i < m; i++) s[b * qpow(a,i) % P] = i; for (LL i = 0; i <= m; i++){ LL tmp = qpow(t,i); if (s.count(tmp)){ ans = i * m - s[tmp]; break; } } if (ans == -1) puts("Orz, I cannot find x!"); else printf("%lld\n",ans); }}int main(){ T = read(); int t = read(); if (t == 1) solve1(); else if (t == 2) solve2(); else solve3(); return 0;}

转载于:https://www.cnblogs.com/Mychael/p/8282796.html

你可能感兴趣的文章

Java过滤器(Filter)与SpringMVC拦截器(Interceptor)之间的关系与区别