preface
Generally, mathematics research in senior high school and below is mainly continuous mathematics
When you think of logarithmic functions, most of you will think of the following function images:
(picture drawn by desmos)
But the logarithm in the modular sense is different
Model
Try to solve the following equation:
That is, the logarithm in the sense of module
BSGS algorithm
Full name: Baby Step Giant Step algorithm
boy step girl step
boy step gay step
with tremendous strength
It's really a very violent practice
PohligHellman? No, I'm really not familiar I haven't even learned Pollard Rho yet
Template: \(\mathtt{Link.}\)
Find the equation in the form of \ (a^x \equiv b \pmod p \) in the time of \ (\ mathcal{O} (\sqrt{p}) \), and must meet \ (a \perp p P \)
It can be found that the solution of the equation \ (x \) satisfies \ (x \in [0,p) \)
Direct enumeration is obviously a bad practice. Consider how to make enumeration even
First, express \ (x \) as \ (A\lceil \sqrt{p} \rceil  B \). It can be found that only the range of \ (A,B \in [0,\sqrt{p}] \) can meet the number within \ ([0,p) \)
So let's write it first:
Substitute this expression into the original formula:
Turn the negative index to the other side:
If \ (a,b \) is known, you can now enumerate all the values of \ (a ^ B, B \) on the right side of the congruence
If the smallest \ (x \) is required, if the \ (a ^ B \) obtained by two \ (B \) are equal in the sense of module \ (p \), only the larger \ (B \) needs to be reserved
Through the above enumeration, establish the mapping from \ (a ^ B \) to \ (B \)
Then enumerate the \ (A \) on the other side, find out \ (a^{A\lceil \sqrt{p} \rceil} \), and then check whether there is A feasible \ (A ^ B \) through mapping
In this way, each set of \ (A,B \) that can be used as the legal solution can be obtained, and then \ (x = A\lceil \sqrt{p} \rceil  B \) is the solution of the equation
It can be found that the speed is greatly accelerated by changing the original violent enumeration \ (x \) to multiply \ (A\lceil \sqrt{p} \rceil  B \)
If you use std::map, there will be one more \ (\ log \), so it's better to use hash table
In this problem: handwritten hash table is faster than__ gnu_pbds::gp_hash_table faster than__ gnu_pbds::cc_hash_table is faster than std::unordered_map is faster than std::map, which is great
\(\texttt{Code}\) :
(with a not very cute hash table)
The constant is too large. Even the handwritten hash table can only enter the fourth page of the optimal solution. What gods are on the first page, Orz
int p,a,b; inline int qpow(int _a,int _b) { int res = 1; while(_b) { if(_b & 1) res = (ll)res * _a % p; _a = (ll)_a * _a % p; _b >>= 1; } return res; } constexpr int SIZ = 360007; struct Hash_table { Hash_table() : cnt(0) {}; int cnt; int hd[SIZ]; struct Node { int key; int val,nxt; }p[1000005]; inline int hash_head(int x) { return x % SIZ; } inline int& operator [] (int k) { int h = hash_head(k); for(int i = hd[h]; i ;i = p[i].nxt) if(p[i].key == k) return p[i].val; p[++cnt] = (Node) {k,0,hd[h]},hd[h] = cnt; return p[cnt].val; } }mp; int BSGS() { const int mx = ceil(sqrtf(p)); int base = b % p; ff(i,1,mx) { base = (ll)base * a % p; mp[base] = i; } base = qpow(a,mx); int prod = 1; ff(i,1,mx) { prod = (ll)prod * base % p; if(mp[prod]) return (((ll)i * mx  mp[prod]) % p + p) % p; } return 1; }
exBSGS algorithm
Super unparalleled algorithm
Xichu overlord algorithm
Template: \(\texttt{Link.}\)
Considering that \ (a,p \) is not necessarily coprime, solve \ (a^x \equiv b \pmod p \)
Vigorously remove \ (\ gcd \)
I was killed by kabaha, Abba, Abba, Abba
\(\texttt{Code}\) :
int gcd(int a,int b) { return b ? gcd(b,a % b) : a; } constexpr int SIZ = 100007; struct Hash_table { Hash_table() : cnt(0) {}; int cnt; int hd[SIZ]; struct Node { int key; int val,nxt; }p[1000005]; inline int hash_head(int x) { return x % SIZ; } inline int& operator [] (int k) { int h = hash_head(k); for(int i = hd[h]; i ;i = p[i].nxt) if(p[i].key == k) return p[i].val; p[++cnt] = (Node) {k,0,hd[h]},hd[h] = cnt; return p[cnt].val; } inline void clear() { cnt = 0,mems(hd,0); } }mp; int BSGS(int a,int b,int p,int pd) { mp.clear(); int mx = ceil(sqrtf(p)); int base = 1; ff(i,1,mx) { base = (ll)base * a % p; mp[(ll)base * b % p] = i; } int prod = pd; ff(i,1,mx) { prod = (ll)prod * base % p; if(mp[prod]) { int res = (((ll)i * mx  mp[prod]) % p + p) % p; if(res >= 0) return res; } } return 1; } int exBSGS(int a,int b,int p) { a %= p,b %= p; if(b == 1  p == 1) return 0; int k = 0; int d,pd = 1; while((d = gcd(a,p)) ^ 1) { if(b % d) return 1; ++k;b /= d,p /= d; pd = (ll)pd * a / d % p; if(pd == b) return k; } int res = BSGS(a,b,p,pd); if(res == 1) return 1; else return res + k; }
Examples
T1
Realize the following three functions:

Finding modular meaning multiplication power

Solving linear congruence equation

Solving higher order congruence equation
The rest of the family is in the bucket
So write fast power, exGCD and BSGS respectively
Be careful without special judgment
T2
P4454 [CQOI2018] crack DH protocol
The subject matter is too long for litigation
After reading, I found that it is the BSGS template
Wuhu, one engine optimal solution!
T3
Me: are you BSGS?
P4861: I'm Euler function
Me: you are BSGS
A \ (N,K \) can be judged as no solution
Then remember that the calculated \ (x \) needs to be greater than \ (0 \)
T4
First, it is found that it is not the familiar form of higherorder congruence equation
Then \ (K \) and \ (m \) are also very large But the time is 2s
??? I can't accept it
First, change the right side of the original formula into exponential form
Congruence can be left and right same Addition & multiplication. Consider using this property
So multiply both sides by \ (9 \) and then add \ (1 \), and the left side will change to the form of \ (10^{N} \)
Then you find that you need to multiply quickly and consider__ int128_ Tthe water passes
As a result, it was adjusted all the time due to incomplete replacement
Finally, the optimal solution is mixed to the third
T5
P3306 [SDOI2013] random number generator
It can be found that the recurrence formula of linear congruence looks like an equal difference sequence
The inverse element is a standard form that BSGS can solve
summary
I don't know if there is a useful technology tree
It's not particularly difficult. It's mainly to push the formula into the form of \ (a^x \equiv b \pmod p \) and then set the board
The board is also very easy to understand
There are so few exBSGS questions
CF1106F is the BSGS question of the underworld. Brush CF1106 tomorrow
CF1106 is Div 2 QAQ