問題一覧 > 教育的問題

No.3577 Fermat Curve

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 30
作問者 : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10522 / 自分の提出
問題文最終更新日: 2026-07-03 11:08:14
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 503 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。