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

Pohlig-Hellman? 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

P2485 [SDOI2011] calculator

Realize the following three functions:

1. Finding modular meaning multiplication power

2. Solving linear congruence equation

3. 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 D-H 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

P4861 button

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

P4884 how many 1?

First, it is found that it is not the familiar form of higher-order 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