No.3577 Fermat Curve
タグ : / 解いたユーザー数 30
作問者 : 👑
Note
The execution time limit for this problem is 4000[ms].
Problem Statement
You are given $2$ positive integers $N, B$ as input.
$\displaystyle x^N + y^N \equiv z^N \pmod{B} $
Find the number of triples $(x,y,z)$ of non-negative integers less than $B$ satisfying the above.
Background
This section explains the background for those familiar with algebraic geometry. The homogeneous equation $x^N + y^N = z^N$ of degree $N$ defines an algebraic surface in the $3$-dimensional affine space $\mathbb{A}^3_{\mathbb{Z}/B \mathbb{Z}}$ over $\textrm{Spec}(\mathbb{Z}/B \mathbb{Z})$ and an algebraic curve in the $2$-dimensional projective space $\mathbb{P}^2_{\mathbb{Z}/B \mathbb{Z}}$. Denote the former algebraic surface by $S$ and the latter algebraic curve by $C$. The value to be computed here is nothing but the number $\# S(\mathbb{Z}/B \mathbb{Z})$ of $\mathbb{Z}/B \mathbb{Z}$-rational points of $S$. Also, $C$ is called the Fermat curve and is an important object of study in arithmetic geometry.
In what follows, assume that $B$ is prime. Then the $\mathbb{Z}/B \mathbb{Z}$-rational points of $C$ correspond exactly to the lines in $S$ passing through the origin, and the number of $\mathbb{Z}/B \mathbb{Z}$-rational points on a line in $S$ passing through the origin equals $B$. Therefore, the number $\# C(\mathbb{Z}/B \mathbb{Z})$ of $\mathbb{Z}/B \mathbb{Z}$-rational points of $C$ can be expressed as $(B-1)^{-1}(\# S(\mathbb{Z}/B \mathbb{Z}) - 1)$, so computing $\# C(\mathbb{Z}/B \mathbb{Z})$ and computing $\# S(\mathbb{Z}/B \mathbb{Z})$ are essentially equivalent.
From the above, when $B$ is prime, this problem is essentially equivalent to counting the $\mathbb{Z}/B \mathbb{Z}$-rational points of the Fermat curve.
Input
The input is given from standard input in $1$ line in the following format:
- The $1$st line contains $N, B$ separated by a single space.
$N$ $B$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^{18}$.
- $B$ is an integer satisfying $1 \leq B \leq 10^4$.
Output
Output in $1$ line the number of triples $(x,y,z)$ of non-negative integers less than $B$ satisfying the condition.
Print a newline at the end.
Sample
Sample 1
Input
1 1
Output
1
Here $(N,B) = (1,1)$. The only triple $(x,y,z)$ of non-negative integers less than $B$ is $(0,0,0)$, and we have
$\displaystyle 0^N + 0^N = 0 = 0^N $
.
Sample 2
Input
1 2
Output
4
Here $(N,B) = (1,2)$. The only triples $(x,y,z)$ of non-negative integers less than $B$ are $(0,0,0), (1,0,0), (0,1,0), (0,0,1), (1,1,0), (1,0,1), (0,1,1), (1,1,1)$, and modulo $B$ we have
$\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} $
.
Sample 3
Input
2 3
Output
9
Here $(N,B) = (2,3)$. There are $9$ triples $(x,y,z)$ satisfying the condition.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。