数论-BSGS大步小步算法

bsgs算法

Baby Step Giant Step算法,简称BSGS算法,也称为大步小步算法.

解决对象

离散对数:当

$x\equiv G^k\pmod m$时,$log_G(x)\equiv k\pmod{\phi(m)}$。此处的$log_G(x)$是$x$以整数$G$为底,模$\phi(m)$的离散对数。
BSGS算法就是用来求解$A^x\equiv B\pmod C$。原始的BSGS算法只能解决$C$是质数的问题。

求解步骤

设$m=\sqrt C$向下取整,$x=i\times m+j$,那么,$A^x=(A^m)^i\times A^j,0\leq i<m,0\leq j<m$。然后可以枚举$i$,这是一个$O(\sqrt C)$级别的枚举。
对于枚举的每一个$i$,都令$D=(A^m)^i$,令$E=A^j$,那么就有$D\times E\equiv B\pmod C$。然后用扩展欧几里得求解。
不过还应该特判$A$是$C$的倍数的情况,比较容易。
对于多次调用$A^j$的情况,不用每次都用快速幂,只需要扔进hash表就可以了。

基本代码(用map模拟hash)

这道题
采用map,代码量比hash少的多了!!
(hash我调了好几天没调出来,后来换成map就过了,肯定是hash写错了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
long long num=0;
char c=' ';
bool flag=true;
for(;c>'9'||c<'0';c=getchar())
if(c=='-')
flag=false;
for(;c>='0'&&c<='9';num=num*10+c-48,c=getchar());
return flag ? num : -num;
}
int A,B,C;
namespace ksm
{
long long qpow(long long a,long long t,long long p)
{
int base=a%p;
long long ans=1;
while(t)
{
if(t&1)
ans=(long long)ans%p*(base%p)%p;
base=(long long)base%p*(base%p)%p;
t>>=1;
}
return ans;
}
}


namespace BSGS
{
map<long long,int>mp;
int bsgs(int A,int B,int C)
{
mp.clear();
if(A%C==0)
return -1;
int p=false;
int m=ceil(sqrt(C));
long long ans;
for(int i=0;i<=m;i++)
{
if(!i)
{
ans=B%C;
mp[ans]=i;
continue;
}
ans=ans*A%C;
mp[ans]=i;
}
long long t=ksm::qpow(A,m,C);ans=1;
for(int i=1;i<=m;i++)
{
ans=(ans*t)%C;
if(mp[ans])
{
int t=i*m-mp[ans];
return (t%C+C)%C;
p=true;
break;
}
}
if(!p)return -1;

}
}

int main()
{
int t=read();
int l=read();
if(l==1)
{
using namespace ksm;
while(t--)
{
int a=read();
int c=read();
int b=read();
printf("%lld\n",qpow(a,c,b));
}
return 0;
}
if(l==2)
{
using namespace ksm;
while(t--)
{
int y=read();
int z=read();
int p=read();
int gcd=__gcd(y,p);
if(z%gcd)
{
printf("Orz, I cannot find x!\n");
continue;
}
printf("%d\n",((z%p)*(long long)qpow(y,p-2,p))%p);
}
}
if(l==3)
{
using namespace BSGS;
using namespace ksm;
while(t--)
{
A=read();B=read();C=read();
long long ans=bsgs(A,B,C);
if(ans==-1)
{
printf("Orz, I cannot find x!\n");
continue;
}
printf("%lld\n",ans);
}
}
return 0;
}

鸣谢这位大佬map的启示!
我是传送门

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 1
2 1 3
2 2 3
2 3 3

输出样例#1:

2
1
2

输入样例#2:

3 2
2 1 3
2 2 3
2 3 3

输出样例#2:

2
1
0

输入样例#3:

4 3
2 1 3
2 2 3
2 3 3
2 4 3

输出样例#3:

0
1
Orz, I cannot find x!
0

数据规模和约定

20% K=1,35% K=2,45% K=3。100% 1<=y,z,P<=10^9,P为质数,1<=T<=10

题解

这里有三种问法,第一种问法就直接是带模的快速幂,没啥好说的。
第二种问法就是求线性方程解,那就用扩展欧几里得!
第三种问法就是本文考虑的BSGS算法,也就是一个板子题目吧。怎么写板子前面已经介绍过了。

code

就是纯板子吧,直接照搬上面的代码就行了。

扩展BSGS

传统的bsgs只能解决c是质数的问题,如果c是合数,那就需要使用扩展bsgs。因为不是质数,所以不能直接求逆元。
扩展BSGS大概有那么几几个步骤:
设$d=gcd(A,C)$,那么$A,B,C$可以表示为$A=ad,B=bd$(如果B不是d的倍数且$B!=1$则显然无解),$C=c*d$。代入原式可得$a\times (a\times d)^{x-1}\equiv b\pmod c$,如果我们把$D\times a$,那么左边就只剩下$(a\times d)^{x-1}了$,不停地求$d=gcd(A,C)$,然后将B和C分别除以d。D要乘A/d,num++,直到d=1为止。
最后方程就成为这种形式了:$D\times A^{x-num}\equiv B\pmod C$。那么令$x=i\times m+j+num$,那么原先的BSGS一样处理就可以了。但是需要注意的是,x<num的时候美剧不到,所以在处理的时候记得对x<num的情况进行单独枚举。

文章目录
  1. 1. bsgs算法
    1. 1.1. 解决对象
    2. 1.2. 求解步骤
    3. 1.3. 基本代码(用map模拟hash)
  2. 2. SDOI2011 计算器
    1. 2.1. 题目描述
    2. 2.2. 输入输出格式
      1. 2.2.1. 输入格式:
      2. 2.2.2. 输出格式:
    3. 2.3. 输入输出样例
      1. 2.3.1. 输入样例#1:
      2. 2.3.2. 输出样例#1:
      3. 2.3.3. 输入样例#2:
      4. 2.3.4. 输出样例#2:
      5. 2.3.5. 输入样例#3:
      6. 2.3.6. 输出样例#3:
    4. 2.4. 数据规模和约定
  3. 3. 题解
    1. 3.1. code
  4. 4. 扩展BSGS