[CQOI2018]破解D-H协议

嘟嘟嘟



这不就是个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;
}