hexo-blog/source/_posts/oi/clever-y.md

---

title: Clever Y tags:

• Baby-Step Giant-Step
• GCD-LCM
• Multiplicative Inverse id: "2371" categories:
• - OI
  • Number Theory date: 2018-03-08 10:55:16 ---

题目描述

Little Y finds there is a very interesting formula in mathematics:

$$ X^Y \bmod Z=K $$

Given $X, Y, Z$, we all know how to figure out $K$ fast. However, given $X, Z, K$, could you figure out $Y$ fast?

题意概述

给定$X, Z, K$，求满足$X^Y \bmod Z=K$的$Y$的最小值。若不存在$0 \le Y \lt Z$满足条件，则输出无解。

数据范围：$0 \le X, Z, K \le 10^9$。

算法分析

显然$K \ge Z$时无解。在其他情况下，条件可以写成

$$ X^Y \equiv K \pmod Z $$

特殊处理两种情况：$X, K$中至少有一个为$0$时，$Y=1$或无解；$K=1$时，$Y=0$。

先考虑$(X, Z)=1$的情况。令$M=\lceil \sqrt{Z} \rceil, \; Y=aM-b \; (0 \lt a, b \le M)$，那么

$$ \begin{align} X^{aM-b} &\equiv K \pmod Z \\ X^{aM} &\equiv K \cdot X^b \pmod Z \end{align} $$

可以在$O(M)$的时间内预处理出$K \cdot X^b$，存在哈希表中，接着$O(M)$枚举$a$，判断哈希表中是否存在$X^{aM}$，若存在，则找到解$Y=aM-b$。由于要求最小值，因此哈希表中有重复时应记录较大的$b$。

下面考虑$(X, Z) \gt 1$的情况。令$D=(X, Z)$，易知若$K \nmid D$则无解。设$X=Dx, \; K=Dk, \; Z=Dz$，据同余的性质可得

$$ \begin{align} (Dx)^Y &\equiv Dk \pmod{Dz} \\ x \cdot (Dx)^{Y-1} &\equiv k \pmod z \end{align} $$

因为$D=(X, Z)$，所以$(x, z)=1$，即$x$在模$z$意义下有逆元，因此

$$ (Dx)^{Y-1} \equiv k \cdot x^{-1} \pmod z $$

令$X'=Dx=X, \; Y'=Y-1, \; K'=k \cdot x^{-1}, \; Z'=z$，则

$$ (X')^{Y'} \equiv K' \pmod{Z'} $$

这和初始时的方程具有一样的形式。若$(X', Z') \gt 1$，则重复以上过程，否则可以参照$(X, Z)=1$的情况。

代码

/*
 * You will be singled out for promotion in your work.
 */

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

class HashTable {
private:
  static int const MOD = 3214567;
  int numr, h[MOD], id[MOD], val[MOD], nxt[MOD];

public:
  void clear() { memset(h, numr = 0, sizeof h); }

int count(int const &n) {
    for (int i = h[n % MOD]; i; i = i[nxt])
      if (i[id] == n)
        return 1;
    return 0;
  }

int &operator[](int const &n) {
    for (int i = h[n % MOD]; i; i = i[nxt])
      if (i[id] == n)
        return i[val];
    ++numr, numr[id] = n, numr[nxt] = h[n % MOD], h[n % MOD] = numr;
    return numr[val];
  }
} mp;

int ex_gcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  int ret = ex_gcd(b, a % b, y, x);
  y -= a / b * x;
  return ret;
}

int get_gcd(int a, int b) {
  int x, y;
  return ex_gcd(a, b, x, y);
}

int get_inv(int a, int b) {
  int x, y;
  return ex_gcd(a, b, x, y), (x + b) % b;
}

int bsgs(int a, int b, int c) {
  a %= c;
  if (a == 0)
    return b == 0 ? 1 : -1;
  if (b == 0)
    return -1;
  if (b == 1)
    return 0;
  int k = 0;
  for (int t; (t = get_gcd(a, c)) > 1; ++k) {
    if (b % t)
      return -1;
    c /= t, b /= t, b = 1ll * b * get_inv(a / t, c) % c;
  }
  mp.clear();
  int d = a, m = sqrt(c) + 1;
  for (int i = 1; i <= m; ++i, d = 1ll * d * a % c)
    mp[1ll * d * b % c] = i;
  d = 1ll * d * get_inv(a, c) % c;
  int e = d;
  for (int i = 1; i <= m; ++i, e = 1ll * e * d % c)
    if (mp.count(e))
      return i * m - mp[e] + k;
  return -1;
}

int main() {
  for (int a, b, c; scanf("%d%d%d", &a, &c, &b), a || b || c;) {
    int ans = bsgs(a, b, c);
    if (~ans)
      printf("%d\n", ans);
    else
      puts("No Solution");
  }
  return 0;
}