Fermat's Last Theorem

题目描述

Given a positive integer $n$ and a positive prime number $p$, find $x, y$ and $z$ such that $x^n+y^n \equiv z^n \pmod p$ and $x, y$ and $z$ are nonzero modulo $p$ or report that there’s no such triple.

题意概述

给定一个整数$n$和一个质数$p$，判断方程$x^n+y^n \equiv z^n \pmod p \ (1 \le x, y, z \lt p)$是否存在整数解，若存在则给出一组解。有$T$组数据。

数据范围：$1 \le T \le 1000, \ 3 \le n \le 10^6, \ 2 \le p \le 10^6$。

算法分析

为了方便，以下同余方程模数均为$p$。

求出$p$的原根$g$，设$x=g^{k_1}, \ y=g^{k_2}, \ z=g^{k_3}$，方程变为

$$
g^{k_1n}+g^{k_2n} \equiv g^{k_3n}
$$

令$G=g^n$，则

$$
G^{k_1}+G^{k_2} \equiv G^{k_3}
$$

由于$g$是原根，可知$G \not \equiv 0$，因此

$$
\begin{align}
G^{k_1-k_2}+1 &\equiv G^{k_3-k_2} \\
G^{k_1-k_3}+G^{k_2-k_3} &\equiv 1
\end{align}
$$

根据费马小定理，$G^{p-1} \equiv 1$，所以只要从$1$到$p-1$枚举$i$，判断是否存在$j \le i$满足

$$
G^i+1 \equiv G^j \lor G^j+1 \equiv G^i \lor G^i+G^j \equiv 1
$$

若存在，则找到了一组解。若枚举到$i$时发现存在$j \lt i$满足$G^i \equiv G^j$，说明开始循环，直接输出无解。根据抽屉原理，枚举的次数不会太多。

此题时限较小，不能每组询问都清空数组，可以使用时间戳。

代码

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

static int const N = 1000005;
int a[N], b[N], pri[N];

int power(int a, int b, int p) {
  int ret = 1;
  for (; b; b >>= 1)
    b & 1 && (ret = 1ll * ret * a % p), a = 1ll * a * a % p;
  return ret;
}

int get_prt(int p) {
  int top = 0, k = p - 1;
  for (int i = 2; i * i <= k; ++i)
    if (!(k % i)) {
      pri[top++] = i;
      for (; !(k % i); k /= i)
        ;
    }
  if (k > 1)
    pri[top++] = k;
  for (int i = 2; i <= p - 1; ++i) {
    bool fg = 1;
    for (int j = 0; fg && j < top; ++j)
      fg &= power(i, (p - 1) / pri[j], p) > 1;
    if (fg)
      return i;
  }
  return 0;
}

int main() {
  int T;
  scanf("%d", &T);
  for (int n, p; T--;) {
    scanf("%d%d", &n, &p);
    int g = get_prt(p), gn = power(g, n, p), x = 0, y = 0, z = 0;
    for (int i = 1, G = gn; i <= p - 1; ++i, G = 1ll * G * gn % p)
      if (b[G] == T + 1)
        break;
      else {
        a[G] = i, b[G] = T + 1;
        if (b[G + 1] == T + 1) {
          x = power(g, i, p), y = 1, z = power(g, a[G + 1], p);
          break;
        }
        if (b[G - 1] == T + 1) {
          x = power(g, a[G - 1], p), y = 1, z = power(g, i, p);
          break;
        }
        if (b[1 - G + p] == T + 1) {
          x = power(g, i, p), y = power(g, a[1 - G + p], p), z = 1;
          break;
        }
      }
    x ? printf("%d %d %d\n", x, y, z) : puts("-1");
  }
  return 0;
}