嘟嘟嘟



这不就是个bsgs板儿嘛。

顺便就复习了一下bsgs和哈希表。

头一次觉得我的博客这么好用，一下就懂了：数论学习笔记之高次不定方程



这里再补充几点：

1.关于这一段代码：

int S = sqrt(c), p = 1;

for(int i = 0; i < S; ++i)

  {

    if(p == b) return i + cnt;

    insert(1LL * p * b % c, i);

    p = 1LL * p * a % c;

  }

for(int i = S, q = p; i - S + 1 < c; i += S)

  {

    int t = query(q);

    if(~t) return i - t + cnt;

    q = 1LL * q * p % c;

  }

这一段是bsgs里最核心的部分。

首先是为什么\(q\)每一次乘以\(p\)：第一层循环后，\(p\)就成为了\(a ^ m\)，这样就相当于\(a ^ {i * m}\)。

然后是第二层循环的终止条件为什么是这个：大家都知道，这一段代码是枚举\(a ^ {tm}\)的，只不过用\(i\)代替了\(tm\)，所以我们考虑\(i\)的最大值：\(tm - y < c \Rightarrow i - (m - 1) < c \Rightarrow i - m + 1 < c\) 。这就出来了。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define In inline

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int base = 99979;

const int maxe = 1e6 + 5;

inline ll read()

{

  ll ans = 0;

  char ch = getchar(), last = ' ';

  while(!isdigit(ch)) last = ch, ch = getchar();

  while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

  if(last == '-') ans = -ans;

  return ans;

}

inline void write(ll x)

{

  if(x < 0) x = -x, putchar('-');

  if(x >= 10) write(x / 10);

  putchar(x % 10 + '0');

}

int g, P, n;

In ll quickpow(ll a, ll b, ll mod)

{

  ll ret = 1;

  for(; b; b >>= 1, a = a * a % mod)

    if(b & 1) ret = ret * a % mod;

  return ret;

}

In ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

In void exgcd(ll a, ll b, ll& x, ll& y)

{

  if(!b) x = 1, y = 0;

  else exgcd(b, a % b, y, x), y -= a / b * x;

}

In ll inv(ll a, ll mod)

{

  ll x, y;

  exgcd(a, mod, x, y);

  return x;

}

struct Hash

{

  int nxt, to, w;

}e[maxe];

int head[base], ecnt = 0;

int st[base], top = 0;

In void init()

{

  ecnt = 0;

  while(top) head[st[top--]] = 0;

}

In void insert(int x, int y)

{

  int h = x % base;

  if(!head[h]) st[++top] = h;

  e[++ecnt] = (Hash){head[h], x, y};

  head[h] = ecnt;

}

In int query(int x)

{

  int h = x % base;

  for(int i = head[h]; i; i = e[i].nxt)

    if(e[i].to == x) return e[i].w;

  return -1;

}

In int bsgs(int a, int b, int c)

{

  int Gcd, d = 1, cnt = 0;

  while((Gcd = gcd(a, c)) ^ 1)

    {

      if(b % Gcd) return -1;

      ++cnt; b /= Gcd, c /= Gcd;

      d = 1LL * d * (a / Gcd) % c;

    }

  b = 1LL * b * inv(d, c) % c;

  init();

  int S = sqrt(c), p = 1;

  for(int i = 0; i < S; ++i)

    {

      if(p == b) return i + cnt;

      insert(1LL * p * b % c, i);

      p = 1LL * p * a % c;

    }

  for(int i = S, q = p; i - S + 1 < c; i += S)

    {

      int t = query(q);

      if(~t) return i - t + cnt;

      q = 1LL * q * p % c;

    }

  return -1;

}

int main()

{

  g = read(), P = read(), n = read();

  for(int i = 1; i <= n; ++i)

    {

      int A = read(), B = read();

      write(quickpow(g, 1LL * bsgs(g, A, P) * bsgs(g, B, P) , P)), enter;

    }

  return 0;

}