No.3577 フェルマー曲線
p-adic注意
この問題の実行時間制限は4000[ms]です。
問題文
入力に $2$ 個の正整数 $N, B$ が与えられます。
$\displaystyle x^N + y^N \equiv z^N \pmod{B} $
を満たす $B$ 未満の非負整数の組 $(x,y,z)$ の個数を求めてください。
背景
代数幾何を知っている人向けに背景を説明します。斉次 $N$ 次方程式 $x^N + y^N = z^N$ は $\textrm{Spec}(\mathbb{Z}/B \mathbb{Z})$ 上の $3$ 次元アフィン空間 $\mathbb{A}^3_{\mathbb{Z}/B \mathbb{Z}}$ 内の代数曲面と $2$ 次元射影空間 $\mathbb{P}^2_{\mathbb{Z}/B \mathbb{Z}}$ 内の代数曲線を定めます。前者の代数曲面と後者の代数曲線をそれぞれ $S$ と $C$ と置きます。今回求める値は $S$ の $\mathbb{Z}/B \mathbb{Z}$-有理点の個数 $\# S(\mathbb{Z}/B \mathbb{Z})$ に他なりません。また $C$ はフェルマー曲線と呼ばれ、数論幾何における重要な研究対象です。
以下、$B$ が素数であるとします。この時 $C$ の $\mathbb{Z}/B \mathbb{Z}$-有理点は $S$ 内の原点を通る直線に正確に対応し、かつ $S$ 内の原点を通る直線における $\mathbb{Z}/B \mathbb{Z}$-有理点の個数は $B$ と一致します。従って $C$ の $\mathbb{Z}/B \mathbb{Z}$-有理点の個数 $\# C(\mathbb{Z}/B \mathbb{Z})$ は $(B-1)^{-1}(\# S(\mathbb{Z}/B \mathbb{Z}) - 1)$ と表すことができ、$\# C(\mathbb{Z}/B \mathbb{Z})$ を求めることと $\# S(\mathbb{Z}/B \mathbb{Z})$ を求めることは実質等価です。
以上より、この問題は $B$ が素数であれば本質的にフェルマー曲線の $\mathbb{Z}/B \mathbb{Z}$-有理点の数え上げ問題と等価です。
入力
入力は以下の形式で標準入力から $1$ 行で与えられます：
- $1$ 行目に $N, B$ が半角空白区切りで与えられます。
$N$ $B$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^{18}$ を満たす整数である。
- $B$ は $1 \leq B \leq 10^4$ を満たす整数である。
出力
条件を満たす $B$ 未満の非負整数の組 $(x,y,z)$ の個数を $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1
出力
1
$(N,B) = (1,1)$ です。$B$ 未満の非負整数の組 $(x,y,z)$ は $(0,0,0)$ のみであり、
$\displaystyle 0^N + 0^N = 0 = 0^N $
です。
サンプル2
入力
1 2
出力
4
$(N,B) = (1,2)$ です。$B$ 未満の非負整数の組 $(x,y,z)$ は $(0,0,0), (1,0,0), (0,1,0), (0,0,1), (1,1,0), (1,0,1), (0,1,1), (1,1,1)$ のみであり、法 $B$ において
$\displaystyle \begin{array}{rcccccl} \displaystyle 0^N + 0^N &\displaystyle = &\displaystyle 0 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle 0 &\displaystyle = &\displaystyle 0^N \\ \displaystyle 1^N + 0^N &\displaystyle = &\displaystyle 1 &\displaystyle \textcolor{red}{\not\equiv} &\displaystyle 0 &\displaystyle = &\displaystyle 0^N \\ \displaystyle 0^N + 1^N &\displaystyle = &\displaystyle 1 &\displaystyle \textcolor{red}{\not\equiv} &\displaystyle 0 &\displaystyle = &\displaystyle 0^N \\ \displaystyle 1^N + 1^N &\displaystyle = &\displaystyle 2 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle 0 &\displaystyle = &\displaystyle 0^N \\ \displaystyle 0^N + 0^N &\displaystyle = &\displaystyle 0 &\displaystyle \textcolor{red}{\not\equiv} &\displaystyle 1 &\displaystyle = &\displaystyle 1^N \\ \displaystyle 1^N + 0^N &\displaystyle = &\displaystyle 1 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle 1 &\displaystyle = &\displaystyle 1^N \\ \displaystyle 0^N + 1^N &\displaystyle = &\displaystyle 1 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle 1 &\displaystyle = &\displaystyle 1^N \\ \displaystyle 1^N + 1^N &\displaystyle = &\displaystyle 2 &\displaystyle \textcolor{red}{\not\equiv} &\displaystyle 1 &\displaystyle = &\displaystyle 1^N \end{array} $
です。
サンプル3
入力
2 3
出力
9
$(N,B) = (2,3)$ です。条件を満たす $(x,y,z)$ は $9$ 個あります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。