计时器【扩展欧几里得+BSGS】

题目：

　　https://www.luogu.org/problemnew/show/P2485

题目简介：

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

　　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。

　　为了拿到奖品，全力以赴吧！

题解：

　　问题一：二分快速幂

 1 ll Make(ll x,ll y,ll mod){
 2     if(y==0) return 1%mod;
 3     ll mid=y/2;
 4     ll ans=Make(x,mid,mod);
 5     ans=(ans*ans)%mod;
 6     if(y&1){ans=(ans*x)%mod;}
 7     return ans; 
 8 }
 9 void Next1(){
10     Read(Y),Read(Z),Read(P);
11     ll ans=Make(Y,Z,P);
12     Write(ans);
13     return ;
14 }

View Code

　　问题二：扩展欧几里得模板

 1 ll ExGcd(ll a,ll b,ll &x,ll &y){
 2     if(b==0) {
 3         x=1;
 4         y=0;
 5         return a;
 6     }
 7     ll res=ExGcd(b,a%b,y,x);
 8     y-=a/b*x;
 9     return res;
10 }
11 void Next2(){
12     Read(Y),Read(Z),Read(P);
13     ll x,y,res;
14     if(Y==0 && Z!=0){
15         printf("Orz, I cannot find x!
");
16         return ;
17     }
18     res=ExGcd(Y,P,x,y);    
19     if(Z%res){
20         printf("Orz, I cannot find x!
");
21         return ;
22     }
23     x=((Z/res*x%P)+P)%(P/res);
24     Write(x);
25     return ;
26 }

View Code

　　问题三：BabyStepGiantStep 【BSGS】

　对于幂取模，直接硬来（枚举指数）时间复杂度是过不去的

　　对于BSGS的理解：

　　　　对于 y^x ≡ z (mod p)

　　　　根据抽屉原理： y^(p+k) mod p 的值一定存在于 y^(1~p) mod p 中（因为mod p最多有p个值）

　　　　所以我们的考虑范围也就从 inf 缩小到了 p，但，这仍然是不够的

　　　　思考继续缩小考虑范围

　　　　想到分治，讲y^(1~p)分解为A部分 y^(1~m) 和B部分 y^(m+1~p)

　　　　考虑两者间的连系

　　　　　　对于B部分的y^j j一定满足 j=x+k*m (k*m 是为了保障x<m)

　　　　　　那么y^j=y^x * y^(k*m)

　　　　　　也就是说我们需要运算的也就化为了m+（p-m）（最坏情况）

　　　　　　为了应对最坏情况选择 m=sqrt（p）

　实现方法（BSGS）：

　　　　根据前面分析，我们只需要预处理 y^(1~m) 的结果（注意离散化储存）

　　　　然后枚举 y^(k*m) 并通过方程： a*y^(k*m)+b*p=z 解出所需值 a （即分析中的 y^x）

　　　　而 a 若是预处理过的值，即找到了原方程的解

 1 const int Hash=100003;
 2 int Tot;
 3 int F[Hash+5];
 4 struct data{
 5     ll to,cost;
 6     int next;
 7 }E[Hash*10];
 8 void Addl(int x,ll y,ll z){
 9     E[++Tot]=(data){y,z,F[x]};
10     F[x]=Tot;
11     return ;
12 }
13 int H(ll x){
14     return abs(x)%Hash;
15 }
16 ll Updata(int op,ll x,ll z){
17     int t=H(x);
18     int i=F[t];
19     while(i){
20         if(E[i].to==x) return E[i].cost;
21         i=E[i].next;
22     }
23     if(op==0) return 0;
24     Addl(t,x,z);
25     return 0;
26 }
27 void Next3(){
28     Read(Y),Read(Z),Read(P);
29     if(Z==1){
30         putchar('0');putchar('
');
31         return ; 
32     }
33     if(Y==0 || Y%P==0){
34         printf("Orz, I cannot find x!
");
35         return ;
36     }
37     Tot=0;
38     ll tmp=1;
39     memset(F,0,sizeof(F));
40     
41     int m=sqrt(P);
42     if(m*m<P) m++;
43     Updata(1,1,m+1);
44     for(ll i=1;i<m;i++){
45         tmp=(tmp*Y)%P;
46         Updata(1,tmp,i);
47     }
48     tmp=(tmp*Y)%P;
49     ll ok=1,x,y;
50     for(ll i=0;i<m;i++){
51         ll res=ExGcd(ok,P,x,y);
52         ll need=(((Z/res*x)%P)+P)%(P/res);
53         ll opi=Updata(0,need,0);
54         if(opi>0){
55             if(opi==m+1) opi=0;
56             Write(opi+m*i);
57             return ;
58         }
59         ok=(ok*tmp)%P;
60     }
61     printf("Orz, I cannot find x!
");
62     return ;
63 }

部分代码

总代码

  1 #include<cmath>
  2 #include<queue>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<iostream>
  6 #include<algorithm>
  7 using namespace std;
  8 typedef long long ll;
  9 int T,K;
 10 ll Y,Z,P;
 11 void Read(ll &x){
 12     x=0;
 13     char c=getchar();
 14     while(!isdigit(c)) c=getchar();
 15     while(isdigit(c)) x=x*10-'0'+c,c=getchar();
 16     return ;
 17 }
 18 ll Make(ll x,ll y,ll mod){
 19     if(y==0) return 1%mod;
 20     ll mid=y/2;
 21     ll ans=Make(x,mid,mod);
 22     ans=(ans*ans)%mod;
 23     if(y&1){ans=(ans*x)%mod;}
 24     return ans; 
 25 }
 26 void Write(ll x){
 27     int np=0;
 28     int s[500];
 29     while(x) s[++np]=x%10,x/=10;
 30     if(!np) s[++np]=0;
 31     while(np) putchar(s[np--]+'0');
 32     putchar('
');
 33     return ;
 34 }
 35 void Next1(){
 36     Read(Y),Read(Z),Read(P);
 37     ll ans=Make(Y,Z,P);
 38     Write(ans);
 39     return ;
 40 }
 41 ll ExGcd(ll a,ll b,ll &x,ll &y){
 42     if(b==0) {
 43         x=1;
 44         y=0;
 45         return a;
 46     }
 47     ll res=ExGcd(b,a%b,y,x);
 48     y-=a/b*x;
 49     return res;
 50 }
 51 void Next2(){
 52     Read(Y),Read(Z),Read(P);
 53     ll x,y,res;
 54     if(Y==0 && Z!=0){
 55         printf("Orz, I cannot find x!
");
 56         return ;
 57     }
 58     res=ExGcd(Y,P,x,y);    
 59     if(Z%res){
 60         printf("Orz, I cannot find x!
");
 61         return ;
 62     }
 63     x=((Z/res*x%P)+P)%(P/res);
 64     Write(x);
 65     return ;
 66 }
 67 const int Hash=100003;
 68 int Tot;
 69 int F[Hash+5];
 70 struct data{
 71     ll to,cost;
 72     int next;
 73 }E[Hash*10];
 74 void Addl(int x,ll y,ll z){
 75     E[++Tot]=(data){y,z,F[x]};
 76     F[x]=Tot;
 77     return ;
 78 }
 79 int H(ll x){
 80     return abs(x)%Hash;
 81 }
 82 ll Updata(int op,ll x,ll z){
 83     int t=H(x);
 84     int i=F[t];
 85     while(i){
 86         if(E[i].to==x) return E[i].cost;
 87         i=E[i].next;
 88     }
 89     if(op==0) return 0;
 90     Addl(t,x,z);
 91     return 0;
 92 }
 93 void Next3(){
 94     Read(Y),Read(Z),Read(P);
 95     if(Z==1){
 96         putchar('0');putchar('
');
 97         return ; 
 98     }
 99     if(Y==0 || Y%P==0){
100         printf("Orz, I cannot find x!
");
101         return ;
102     }
103     Tot=0;
104     ll tmp=1;
105     memset(F,0,sizeof(F));
106     
107     int m=sqrt(P);
108     if(m*m<P) m++;
109     Updata(1,1,m+1);
110     for(ll i=1;i<m;i++){
111         tmp=(tmp*Y)%P;
112         Updata(1,tmp,i);
113     }
114     tmp=(tmp*Y)%P;
115     ll ok=1,x,y;
116     for(ll i=0;i<m;i++){
117         ll res=ExGcd(ok,P,x,y);
118         ll need=(((Z/res*x)%P)+P)%(P/res);
119         ll opi=Updata(0,need,0);
120         if(opi>0){
121             if(opi==m+1) opi=0;
122             Write(opi+m*i);
123             return ;
124         }
125         ok=(ok*tmp)%P;
126     }
127     printf("Orz, I cannot find x!
");
128     return ;
129 }
130 int main(){
131     scanf("%d%d",&T,&K);
132     while(T--)
133     if(K==1) Next1();
134     else if(K==2) Next2();
135     else Next3(); 
136     return 0;
137 }

Code

计时器 【扩展欧几里得+BSGS】

计时器【扩展欧几里得+BSGS】