# 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.

## 算法分析

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

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

\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^i+1 \equiv G^j \lor G^j+1 \equiv G^i \lor G^i+G^j \equiv 1$$

## 代码

#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;
}


418 I'm a teapot