bzoj 2242 [SDOI2011]计算器（数论知识）

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

【思路】

快速幂，拓展欧几里得，BSGS

第一问快速幂求得。

第二问求axΞ b(mod n)，转化为ax=ny+b，转化为ax+ny=b，利用拓展欧几里得算法求出ax+ny=gcd(a,n)，如果b不是gcd的倍数则无解否则为x/gcd*b。

第三问求a^{x Ξ}b(mod n)，BSGS算法。我们需要验证0..n-1内的数。分块，设每块大小为m，求出0..m-1内的aⁱ% n保存为ei，对于m..2m-1内的数，我们只需要验证是否存在有a^m*ei=b(mod n)，即判断是否存在ei=a^-m*b (mod n)，这样用一个hash表存一下ei然后求一下在模n下a^m的逆元就可以了。

时间复杂度为O((m+n/m)logm)，当m取n^½的时候复杂度较优为O(n^½logn)

【代码】

 1 #include<map>
 2 #include<cmath>
 3 #include<cstdio>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 LL a,b,c,T,k;
 8 
 9 LL pow(LL x,LL p,LL MOD) {
10     LL tmp=x,ans=1;
11     while(p) {
12         if(p&1) ans=(ans*tmp)%MOD;
13         tmp=(tmp*tmp)%MOD;
14         p>>=1; 
15     }
16     return ans;
17 }
18 void gcd(LL a,LL b,LL& d,LL& x,LL& y) {
19     if(!b) d=a,x=1,y=0;
20     else gcd(b,a%b,d,y,x),y-=x*(a/b);
21 }
22 LL inv(LL a,LL n) {
23     LL d,x,y;
24     gcd(a,n,d,x,y);
25     return d==1? (x+n)%n:-1;
26 }
27 LL log_mod(LL a,LL b,LL n) {
28     LL m,v,e=1,i;
29     m=sqrt(n+0.5);
30     v=inv(pow(a,m,n),n);
31     map<LL,LL> mp;
32     mp[1]=0;
33     for(LL i=1;i<m;i++) {
34         e=(e*a)%n;
35         if(!mp.count(e)) mp[e]=i;
36     }
37     for(LL i=0;i<m;i++) {
38         if(mp.count(b)) return i*m+mp[b];
39         b=(b*v)%n;
40     }
41     return -1;
42 }
43 
44 int main() {
45     scanf("%lld%lld",&T,&k);
46     while(T--) {
47         scanf("%lld%lld%lld",&a,&b,&c);
48         if(k==1) {
49             printf("%lld
",pow(a,b,c));
50         } else 
51         if(k==2) {
52             LL d,x,y;
53             gcd(a,c,d,x,y);
54             if(b%d) puts("Orz, I cannot find x!");
55             else {
56                 LL ans=((x*b/d)%c+c)%c;
57                 printf("%lld
",ans);
58             }
59         } else {
60             LL ans=log_mod(a,b,c);
61             if(ans==-1) puts("Orz, I cannot find x!");
62             else printf("%lld
",ans);
63         }
64     }
65     return 0;
66 }