BSGS / 扩展BSGS模板

前言

本文介绍BSGS / 扩展BSGS模板 以洛谷P3846为例

一、题目

题目链接: P3846

二、代码及思路 1.思路

对于同余方程 a x ≡ b ( m o d c ) a^x \equiv b \pmod c ax≡b(modc) 我们想去求它的解x，方法是开方后哈希 详见链接: OIWIKI 代码模板为扩展BSGS，即可以解决 a,c不互素的情况 当a,c已知地互素时，可将模板里的exBSGS部分注释起来，变成原始BSGS

2.代码

代码如下：

#include 
#include 
#include 
#define int long long
using namespace std;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int quickpow(int x, int n, int mod) {
  int ans = 1;
  while (n) {
    if (n & 1) ans = (ans * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return ans;
}

int BSGS(int a, int b, int c) {  // a ^ x = b (mod c)
  int n = 0, A = 1;
  // exBSGS start
  int d = gcd(a, c);
  while (d != 1) {
    if (b % d) return -1;
    b /= d, c /= d;
    A = (A * (a / d)) % c;
    n++;  // A * a ^ (x - n) = b (mod c)
    if (A == b) return n;
    d = gcd(a, c);
  }
  // exBSGS end
  int up = ceil(sqrt(c));  // up * up