2242: [SDOI2011]计算器
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 4741 Solved: 1796
[Submit][Status][Discuss]
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。
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
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<iostream>
#include<cstdio>
#include<map>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
inline LL RD(){LL 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 << 1) + (out << 3) + c - '0'; c = getchar();}return out * flag;
}
LL T;
LL qpow(LL a,LL b,LL p){LL ans = 1;for (; b; b >>= 1,a = a * a % p)if (b & 1) ans = ans * a % p;return ans;
}
void exgcd(LL a,LL b,LL& d,LL& x,LL& y){if (!b) {d = a; x = 1; y = 0;}else exgcd(b,a % b,d,y,x),y -= (a / b) * x;
}
LL gcd(LL a,LL b){return !b ? a : gcd(b,a % b);}
void solve1(){LL y,z,p;while (T--){y = RD(); z = RD(); p = RD();printf("%lld\n",qpow(y,z,p));}
}
void solve2(){LL a,c,b,x,y,d,b0;while (T--){a = RD(); c = RD(); b = RD();exgcd(a,b,d,x,y);if (c % d) printf("Orz, I cannot find x!\n");else {x = x * c / d; b0 = b / d;printf("%lld\n",(x % b0 + b0) % b0);}}
}
map<LL,LL> hash;
void solve3(){LL y,z,p,m,t,temp,ans;while (T--){hash.clear();y = RD(); z = RD(); p = RD(); m = (LL)sqrt(p); t = qpow(y,m,p); ans = -1;if (y % p == 0 && z % p) {printf("Orz, I cannot find x!\n"); continue;}else if (y % p == 0 && z % p == 0) printf("1\n");for (LL j = 0; j < m; j++) hash[z * qpow(y,j,p) % p] = j;for (LL i = 1; i <= m; i++) if (hash.count(temp = qpow(t,i,p))){ans = i * m - hash[temp]; break;}if (ans < 0) printf("Orz, I cannot find x!\n");else printf("%lld\n",ans);}
}
int main(){T = RD(); LL K = RD();if (K == 1) solve1();else if (K == 2) solve2();else solve3();return 0;
}